/*M///////////////////////////////////////////////////////////////////////////////////////
//
//  IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
//
//  By downloading, copying, installing or using the software you agree to this license.
//  If you do not agree to this license, do not download, install,
//  copy or use the software.
//
//
//                        Intel License Agreement
//                For Open Source Computer Vision Library
//
// Copyright (C) 2000, Intel Corporation, all rights reserved.
// Third party copyrights are property of their respective owners.
//
// Redistribution and use in source and binary forms, with or without modification,
// are permitted provided that the following conditions are met:
//
//   * Redistribution's of source code must retain the above copyright notice,
//     this list of conditions and the following disclaimer.
//
//   * Redistribution's in binary form must reproduce the above copyright notice,
//     this list of conditions and the following disclaimer in the documentation
//     and/or other materials provided with the distribution.
//
//   * The name of Intel Corporation may not be used to endorse or promote products
//     derived from this software without specific prior written permission.
//
// This software is provided by the copyright holders and contributors "as is" and
// any express or implied warranties, including, but not limited to, the implied
// warranties of merchantability and fitness for a particular purpose are disclaimed.
// In no event shall the Intel Corporation or contributors be liable for any direct,
// indirect, incidental, special, exemplary, or consequential damages
// (including, but not limited to, procurement of substitute goods or services;
// loss of use, data, or profits; or business interruption) however caused
// and on any theory of liability, whether in contract, strict liability,
// or tort (including negligence or otherwise) arising in any way out of
// the use of this software, even if advised of the possibility of such damage.
//
//M*/

#ifdef HAVE_CONFIG_H
#include "cvconfig.h"
#endif

#ifdef HAVE_MALLOC_H
#include <malloc.h>
#endif

#ifdef HAVE_MEMORY_H
#include <memory.h>
#endif

#ifdef _OPENMP
#include <omp.h>
#endif /* _OPENMP */

#include <cstdio>
#include <cfloat>
#include <cmath>
#include <ctime>
#include <climits>

#include "_cvcommon.h"
#include "cvclassifier.h"

#ifdef _OPENMP
#include "omp.h"
#endif

#define CV_BOOST_IMPL

typedef struct CvValArray {
	uchar* data;
	size_t step;
} CvValArray;

#define CMP_VALUES( idx1, idx2 )                                 \
    ( *( (float*) (aux->data + ((int) (idx1)) * aux->step ) ) <  \
      *( (float*) (aux->data + ((int) (idx2)) * aux->step ) ) )

CV_IMPLEMENT_QSORT_EX( icvSortIndexedValArray_16s, short, CMP_VALUES, CvValArray* )

CV_IMPLEMENT_QSORT_EX( icvSortIndexedValArray_32s, int,   CMP_VALUES, CvValArray* )

CV_IMPLEMENT_QSORT_EX( icvSortIndexedValArray_32f, float, CMP_VALUES, CvValArray* )

CV_BOOST_IMPL
void cvGetSortedIndices( CvMat* val, CvMat* idx, int sortcols ) {
	int idxtype = 0;
	size_t istep = 0;
	size_t jstep = 0;

	int i = 0;
	int j = 0;

	CvValArray va;

	CV_Assert( idx != NULL );
	CV_Assert( val != NULL );

	idxtype = CV_MAT_TYPE( idx->type );
	CV_Assert( idxtype == CV_16SC1 || idxtype == CV_32SC1 || idxtype == CV_32FC1 );
	CV_Assert( CV_MAT_TYPE( val->type ) == CV_32FC1 );
	if ( sortcols ) {
		CV_Assert( idx->rows == val->cols );
		CV_Assert( idx->cols == val->rows );
		istep = CV_ELEM_SIZE( val->type );
		jstep = val->step;
	} else {
		CV_Assert( idx->rows == val->rows );
		CV_Assert( idx->cols == val->cols );
		istep = val->step;
		jstep = CV_ELEM_SIZE( val->type );
	}

	va.data = val->data.ptr;
	va.step = jstep;
	switch ( idxtype ) {
	case CV_16SC1:
		for ( i = 0; i < idx->rows; i++ ) {
			for ( j = 0; j < idx->cols; j++ ) {
				CV_MAT_ELEM( *idx, short, i, j ) = (short) j;
			}
			icvSortIndexedValArray_16s( (short*) (idx->data.ptr + (size_t)i * idx->step),
										idx->cols, &va );
			va.data += istep;
		}
		break;

	case CV_32SC1:
		for ( i = 0; i < idx->rows; i++ ) {
			for ( j = 0; j < idx->cols; j++ ) {
				CV_MAT_ELEM( *idx, int, i, j ) = j;
			}
			icvSortIndexedValArray_32s( (int*) (idx->data.ptr + (size_t)i * idx->step),
										idx->cols, &va );
			va.data += istep;
		}
		break;

	case CV_32FC1:
		for ( i = 0; i < idx->rows; i++ ) {
			for ( j = 0; j < idx->cols; j++ ) {
				CV_MAT_ELEM( *idx, float, i, j ) = (float) j;
			}
			icvSortIndexedValArray_32f( (float*) (idx->data.ptr + (size_t)i * idx->step),
										idx->cols, &va );
			va.data += istep;
		}
		break;

	default:
		assert( 0 );
		break;
	}
}

CV_BOOST_IMPL
void cvReleaseStumpClassifier( CvClassifier** classifier ) {
	cvFree( classifier );
	*classifier = 0;
}

CV_BOOST_IMPL
float cvEvalStumpClassifier( CvClassifier* classifier, CvMat* sample ) {
	assert( classifier != NULL );
	assert( sample != NULL );
	assert( CV_MAT_TYPE( sample->type ) == CV_32FC1 );

	if ( (CV_MAT_ELEM( (*sample), float, 0,
					   ((CvStumpClassifier*) classifier)->compidx )) <
			((CvStumpClassifier*) classifier)->threshold ) {
		return ((CvStumpClassifier*) classifier)->left;
	}
	return ((CvStumpClassifier*) classifier)->right;
}

#define ICV_DEF_FIND_STUMP_THRESHOLD( suffix, type, error )                              \
CV_BOOST_IMPL int icvFindStumpThreshold_##suffix(                                              \
        uchar* data, size_t datastep,                                                    \
        uchar* wdata, size_t wstep,                                                      \
        uchar* ydata, size_t ystep,                                                      \
        uchar* idxdata, size_t idxstep, int num,                                         \
        float* lerror,                                                                   \
        float* rerror,                                                                   \
        float* threshold, float* left, float* right,                                     \
        float* sumw, float* sumwy, float* sumwyy )                                       \
{                                                                                        \
    int found = 0;                                                                       \
    float wyl  = 0.0F;                                                                   \
    float wl   = 0.0F;                                                                   \
    float wyyl = 0.0F;                                                                   \
    float wyr  = 0.0F;                                                                   \
    float wr   = 0.0F;                                                                   \
                                                                                         \
    float curleft  = 0.0F;                                                               \
    float curright = 0.0F;                                                               \
    float* prevval = NULL;                                                               \
    float* curval  = NULL;                                                               \
    float curlerror = 0.0F;                                                              \
    float currerror = 0.0F;                                                              \
    float wposl;                                                                         \
    float wposr;                                                                         \
                                                                                         \
    int i = 0;                                                                           \
    int idx = 0;                                                                         \
                                                                                         \
    wposl = wposr = 0.0F;                                                                \
    if( *sumw == FLT_MAX )                                                               \
    {                                                                                    \
        /* calculate sums */                                                             \
        float *y = NULL;                                                                 \
        float *w = NULL;                                                                 \
        float wy = 0.0F;                                                                 \
                                                                                         \
        *sumw   = 0.0F;                                                                  \
        *sumwy  = 0.0F;                                                                  \
        *sumwyy = 0.0F;                                                                  \
        for( i = 0; i < num; i++ )                                                       \
        {                                                                                \
            idx = (int) ( *((type*) (idxdata + i*idxstep)) );                            \
            w = (float*) (wdata + idx * wstep);                                          \
            *sumw += *w;                                                                 \
            y = (float*) (ydata + idx * ystep);                                          \
            wy = (*w) * (*y);                                                            \
            *sumwy += wy;                                                                \
            *sumwyy += wy * (*y);                                                        \
        }                                                                                \
    }                                                                                    \
                                                                                         \
    for( i = 0; i < num; i++ )                                                           \
    {                                                                                    \
        idx = (int) ( *((type*) (idxdata + i*idxstep)) );                                \
        curval = (float*) (data + idx * datastep);                                       \
         /* for debug purpose */                                                         \
        if( i > 0 ) assert( (*prevval) <= (*curval) );                                   \
                                                                                         \
        wyr  = *sumwy - wyl;                                                             \
        wr   = *sumw  - wl;                                                              \
                                                                                         \
        if( wl > 0.0 ) curleft = wyl / wl;                                               \
        else curleft = 0.0F;                                                             \
                                                                                         \
        if( wr > 0.0 ) curright = wyr / wr;                                              \
        else curright = 0.0F;                                                            \
                                                                                         \
        error                                                                            \
                                                                                         \
        if( curlerror + currerror < (*lerror) + (*rerror) )                              \
        {                                                                                \
            (*lerror) = curlerror;                                                       \
            (*rerror) = currerror;                                                       \
            *threshold = *curval;                                                        \
            if( i > 0 ) {                                                                \
                *threshold = 0.5F * (*threshold + *prevval);                             \
            }                                                                            \
            *left  = curleft;                                                            \
            *right = curright;                                                           \
            found = 1;                                                                   \
        }                                                                                \
                                                                                         \
        do                                                                               \
        {                                                                                \
            wl  += *((float*) (wdata + idx * wstep));                                    \
            wyl += (*((float*) (wdata + idx * wstep)))                                   \
                * (*((float*) (ydata + idx * ystep)));                                   \
            wyyl += *((float*) (wdata + idx * wstep))                                    \
                * (*((float*) (ydata + idx * ystep)))                                    \
                * (*((float*) (ydata + idx * ystep)));                                   \
        }                                                                                \
        while( (++i) < num &&                                                            \
            ( *((float*) (data + (idx =                                                  \
                (int) ( *((type*) (idxdata + i*idxstep))) ) * datastep))                 \
                == *curval ) );                                                          \
        --i;                                                                             \
        prevval = curval;                                                                \
    } /* for each value */                                                               \
                                                                                         \
    return found;                                                                        \
}

/* misclassification error
 * err = MIN( wpos, wneg );
 */
#define ICV_DEF_FIND_STUMP_THRESHOLD_MISC( suffix, type )                                \
    ICV_DEF_FIND_STUMP_THRESHOLD( misc_##suffix, type,                                   \
        wposl = 0.5F * ( wl + wyl );                                                     \
        wposr = 0.5F * ( wr + wyr );                                                     \
        curleft = 0.5F * ( 1.0F + curleft );                                             \
        curright = 0.5F * ( 1.0F + curright );                                           \
        curlerror = MIN( wposl, wl - wposl );                                            \
        currerror = MIN( wposr, wr - wposr );                                            \
    )

/* gini error
 * err = 2 * wpos * wneg /(wpos + wneg)
 */
#define ICV_DEF_FIND_STUMP_THRESHOLD_GINI( suffix, type )                                \
    ICV_DEF_FIND_STUMP_THRESHOLD( gini_##suffix, type,                                   \
        wposl = 0.5F * ( wl + wyl );                                                     \
        wposr = 0.5F * ( wr + wyr );                                                     \
        curleft = 0.5F * ( 1.0F + curleft );                                             \
        curright = 0.5F * ( 1.0F + curright );                                           \
        curlerror = 2.0F * wposl * ( 1.0F - curleft );                                   \
        currerror = 2.0F * wposr * ( 1.0F - curright );                                  \
    )

#define CV_ENTROPY_THRESHOLD FLT_MIN

/* entropy error
 * err = - wpos * log(wpos / (wpos + wneg)) - wneg * log(wneg / (wpos + wneg))
 */
#define ICV_DEF_FIND_STUMP_THRESHOLD_ENTROPY( suffix, type )                             \
    ICV_DEF_FIND_STUMP_THRESHOLD( entropy_##suffix, type,                                \
        wposl = 0.5F * ( wl + wyl );                                                     \
        wposr = 0.5F * ( wr + wyr );                                                     \
        curleft = 0.5F * ( 1.0F + curleft );                                             \
        curright = 0.5F * ( 1.0F + curright );                                           \
        curlerror = currerror = 0.0F;                                                    \
        if( curleft > CV_ENTROPY_THRESHOLD )                                             \
            curlerror -= wposl * logf( curleft );                                        \
        if( curleft < 1.0F - CV_ENTROPY_THRESHOLD )                                      \
            curlerror -= (wl - wposl) * logf( 1.0F - curleft );                          \
                                                                                         \
        if( curright > CV_ENTROPY_THRESHOLD )                                            \
            currerror -= wposr * logf( curright );                                       \
        if( curright < 1.0F - CV_ENTROPY_THRESHOLD )                                     \
            currerror -= (wr - wposr) * logf( 1.0F - curright );                         \
    )

/* least sum of squares error */
#define ICV_DEF_FIND_STUMP_THRESHOLD_SQ( suffix, type )                                  \
    ICV_DEF_FIND_STUMP_THRESHOLD( sq_##suffix, type,                                     \
        /* calculate error (sum of squares)          */                                  \
        /* err = sum( w * (y - left(rigt)Val)^2 )    */                                  \
        curlerror = wyyl + curleft * curleft * wl - 2.0F * curleft * wyl;                \
        currerror = (*sumwyy) - wyyl + curright * curright * wr - 2.0F * curright * wyr; \
    )

ICV_DEF_FIND_STUMP_THRESHOLD_MISC( 16s, short )

ICV_DEF_FIND_STUMP_THRESHOLD_MISC( 32s, int )

ICV_DEF_FIND_STUMP_THRESHOLD_MISC( 32f, float )


ICV_DEF_FIND_STUMP_THRESHOLD_GINI( 16s, short )

ICV_DEF_FIND_STUMP_THRESHOLD_GINI( 32s, int )

ICV_DEF_FIND_STUMP_THRESHOLD_GINI( 32f, float )


ICV_DEF_FIND_STUMP_THRESHOLD_ENTROPY( 16s, short )

ICV_DEF_FIND_STUMP_THRESHOLD_ENTROPY( 32s, int )

ICV_DEF_FIND_STUMP_THRESHOLD_ENTROPY( 32f, float )


ICV_DEF_FIND_STUMP_THRESHOLD_SQ( 16s, short )

ICV_DEF_FIND_STUMP_THRESHOLD_SQ( 32s, int )

ICV_DEF_FIND_STUMP_THRESHOLD_SQ( 32f, float )

typedef int (*CvFindThresholdFunc)( uchar* data, size_t datastep,
									uchar* wdata, size_t wstep,
									uchar* ydata, size_t ystep,
									uchar* idxdata, size_t idxstep, int num,
									float* lerror,
									float* rerror,
									float* threshold, float* left, float* right,
									float* sumw, float* sumwy, float* sumwyy );

CvFindThresholdFunc findStumpThreshold_16s[4] = {
	icvFindStumpThreshold_misc_16s,
	icvFindStumpThreshold_gini_16s,
	icvFindStumpThreshold_entropy_16s,
	icvFindStumpThreshold_sq_16s
};

CvFindThresholdFunc findStumpThreshold_32s[4] = {
	icvFindStumpThreshold_misc_32s,
	icvFindStumpThreshold_gini_32s,
	icvFindStumpThreshold_entropy_32s,
	icvFindStumpThreshold_sq_32s
};

CvFindThresholdFunc findStumpThreshold_32f[4] = {
	icvFindStumpThreshold_misc_32f,
	icvFindStumpThreshold_gini_32f,
	icvFindStumpThreshold_entropy_32f,
	icvFindStumpThreshold_sq_32f
};

CV_BOOST_IMPL
CvClassifier* cvCreateStumpClassifier( CvMat* trainData,
									   int flags,
									   CvMat* trainClasses,
									   CvMat* /*typeMask*/,
									   CvMat* missedMeasurementsMask,
									   CvMat* compIdx,
									   CvMat* sampleIdx,
									   CvMat* weights,
									   CvClassifierTrainParams* trainParams
									 ) {
	CvStumpClassifier* stump = NULL;
	int m = 0; /* number of samples */
	int n = 0; /* number of components */
	uchar* data = NULL;
	int cstep   = 0;
	int sstep   = 0;
	uchar* ydata = NULL;
	int ystep    = 0;
	uchar* idxdata = NULL;
	int idxstep    = 0;
	int l = 0; /* number of indices */
	uchar* wdata = NULL;
	int wstep    = 0;

	int* idx = NULL;
	int i = 0;

	float sumw   = FLT_MAX;
	float sumwy  = FLT_MAX;
	float sumwyy = FLT_MAX;

	CV_Assert( trainData != NULL );
	CV_Assert( CV_MAT_TYPE( trainData->type ) == CV_32FC1 );
	CV_Assert( trainClasses != NULL );
	CV_Assert( CV_MAT_TYPE( trainClasses->type ) == CV_32FC1 );
	CV_Assert( missedMeasurementsMask == NULL );
	CV_Assert( compIdx == NULL );
	CV_Assert( weights != NULL );
	CV_Assert( CV_MAT_TYPE( weights->type ) == CV_32FC1 );
	CV_Assert( trainParams != NULL );

	data = trainData->data.ptr;
	if ( CV_IS_ROW_SAMPLE( flags ) ) {
		cstep = CV_ELEM_SIZE( trainData->type );
		sstep = trainData->step;
		m = trainData->rows;
		n = trainData->cols;
	} else {
		sstep = CV_ELEM_SIZE( trainData->type );
		cstep = trainData->step;
		m = trainData->cols;
		n = trainData->rows;
	}

	ydata = trainClasses->data.ptr;
	if ( trainClasses->rows == 1 ) {
		assert( trainClasses->cols == m );
		ystep = CV_ELEM_SIZE( trainClasses->type );
	} else {
		assert( trainClasses->rows == m );
		ystep = trainClasses->step;
	}

	wdata = weights->data.ptr;
	if ( weights->rows == 1 ) {
		assert( weights->cols == m );
		wstep = CV_ELEM_SIZE( weights->type );
	} else {
		assert( weights->rows == m );
		wstep = weights->step;
	}

	l = m;
	if ( sampleIdx != NULL ) {
		assert( CV_MAT_TYPE( sampleIdx->type ) == CV_32FC1 );

		idxdata = sampleIdx->data.ptr;
		if ( sampleIdx->rows == 1 ) {
			l = sampleIdx->cols;
			idxstep = CV_ELEM_SIZE( sampleIdx->type );
		} else {
			l = sampleIdx->rows;
			idxstep = sampleIdx->step;
		}
		assert( l <= m );
	}

	idx = (int*) cvAlloc( l * sizeof( int ) );
	stump = (CvStumpClassifier*) cvAlloc( sizeof( CvStumpClassifier) );

	/* START */
	memset( (void*) stump, 0, sizeof( CvStumpClassifier ) );

	stump->eval = cvEvalStumpClassifier;
	stump->tune = NULL;
	stump->save = NULL;
	stump->release = cvReleaseStumpClassifier;

	stump->lerror = FLT_MAX;
	stump->rerror = FLT_MAX;
	stump->left  = 0.0F;
	stump->right = 0.0F;

	/* copy indices */
	if ( sampleIdx != NULL ) {
		for ( i = 0; i < l; i++ ) {
			idx[i] = (int) * ((float*) (idxdata + i * idxstep));
		}
	} else {
		for ( i = 0; i < l; i++ ) {
			idx[i] = i;
		}
	}

	for ( i = 0; i < n; i++ ) {
		CvValArray va;

		va.data = data + i * ((size_t) cstep);
		va.step = sstep;
		icvSortIndexedValArray_32s( idx, l, &va );
		if ( findStumpThreshold_32s[(int) ((CvStumpTrainParams*) trainParams)->error]
				( data + i * ((size_t) cstep), sstep,
				  wdata, wstep, ydata, ystep, (uchar*) idx, sizeof( int ), l,
				  &(stump->lerror), &(stump->rerror),
				  &(stump->threshold), &(stump->left), &(stump->right),
				  &sumw, &sumwy, &sumwyy ) ) {
			stump->compidx = i;
		}
	} /* for each component */

	/* END */

	cvFree( &idx );

	if ( ((CvStumpTrainParams*) trainParams)->type == CV_CLASSIFICATION_CLASS ) {
		stump->left = 2.0F * (stump->left >= 0.5F) - 1.0F;
		stump->right = 2.0F * (stump->right >= 0.5F) - 1.0F;
	}

	return (CvClassifier*) stump;
}

/*
 * cvCreateMTStumpClassifier
 *
 * Multithreaded stump classifier constructor
 * Includes huge train data support through callback function
 */
CV_BOOST_IMPL
CvClassifier* cvCreateMTStumpClassifier( CvMat* trainData,
		int flags,
		CvMat* trainClasses,
		CvMat* /*typeMask*/,
		CvMat* missedMeasurementsMask,
		CvMat* compIdx,
		CvMat* sampleIdx,
		CvMat* weights,
		CvClassifierTrainParams* trainParams ) {
	CvStumpClassifier* stump = NULL;
	int m = 0; /* number of samples */
	int n = 0; /* number of components */
	uchar* data = NULL;
	size_t cstep   = 0;
	size_t sstep   = 0;
	int    datan   = 0; /* num components */
	uchar* ydata = NULL;
	size_t ystep = 0;
	uchar* idxdata = NULL;
	size_t idxstep = 0;
	int    l = 0; /* number of indices */
	uchar* wdata = NULL;
	size_t wstep = 0;

	uchar* sorteddata = NULL;
	int    sortedtype    = 0;
	size_t sortedcstep   = 0; /* component step */
	size_t sortedsstep   = 0; /* sample step */
	int    sortedn       = 0; /* num components */
	int    sortedm       = 0; /* num samples */

	char* filter = NULL;
	int i = 0;

	int compidx = 0;
	int stumperror;
	int portion;

	/* private variables */
	CvMat mat;
	CvValArray va;
	float lerror;
	float rerror;
	float left;
	float right;
	float threshold;
	int optcompidx;

	float sumw;
	float sumwy;
	float sumwyy;

	int t_compidx;
	int t_n;

	int ti;
	int tj;
	int tk;

	uchar* t_data;
	size_t t_cstep;
	size_t t_sstep;

	size_t matcstep;
	size_t matsstep;

	int* t_idx;
	/* end private variables */

	CV_Assert( trainParams != NULL );
	CV_Assert( trainClasses != NULL );
	CV_Assert( CV_MAT_TYPE( trainClasses->type ) == CV_32FC1 );
	CV_Assert( missedMeasurementsMask == NULL );
	CV_Assert( compIdx == NULL );

	stumperror = (int) ((CvMTStumpTrainParams*) trainParams)->error;

	ydata = trainClasses->data.ptr;
	if ( trainClasses->rows == 1 ) {
		m = trainClasses->cols;
		ystep = CV_ELEM_SIZE( trainClasses->type );
	} else {
		m = trainClasses->rows;
		ystep = trainClasses->step;
	}

	wdata = weights->data.ptr;
	if ( weights->rows == 1 ) {
		CV_Assert( weights->cols == m );
		wstep = CV_ELEM_SIZE( weights->type );
	} else {
		CV_Assert( weights->rows == m );
		wstep = weights->step;
	}

	if ( ((CvMTStumpTrainParams*) trainParams)->sortedIdx != NULL ) {
		sortedtype =
			CV_MAT_TYPE( ((CvMTStumpTrainParams*) trainParams)->sortedIdx->type );
		assert( sortedtype == CV_16SC1 || sortedtype == CV_32SC1
				|| sortedtype == CV_32FC1 );
		sorteddata = ((CvMTStumpTrainParams*) trainParams)->sortedIdx->data.ptr;
		sortedsstep = CV_ELEM_SIZE( sortedtype );
		sortedcstep = ((CvMTStumpTrainParams*) trainParams)->sortedIdx->step;
		sortedn = ((CvMTStumpTrainParams*) trainParams)->sortedIdx->rows;
		sortedm = ((CvMTStumpTrainParams*) trainParams)->sortedIdx->cols;
	}

	if ( trainData == NULL ) {
		assert( ((CvMTStumpTrainParams*) trainParams)->getTrainData != NULL );
		n = ((CvMTStumpTrainParams*) trainParams)->numcomp;
		assert( n > 0 );
	} else {
		assert( CV_MAT_TYPE( trainData->type ) == CV_32FC1 );
		data = trainData->data.ptr;
		if ( CV_IS_ROW_SAMPLE( flags ) ) {
			cstep = CV_ELEM_SIZE( trainData->type );
			sstep = trainData->step;
			assert( m == trainData->rows );
			datan = n = trainData->cols;
		} else {
			sstep = CV_ELEM_SIZE( trainData->type );
			cstep = trainData->step;
			assert( m == trainData->cols );
			datan = n = trainData->rows;
		}
		if ( ((CvMTStumpTrainParams*) trainParams)->getTrainData != NULL ) {
			n = ((CvMTStumpTrainParams*) trainParams)->numcomp;
		}
	}
	assert( datan <= n );

	if ( sampleIdx != NULL ) {
		assert( CV_MAT_TYPE( sampleIdx->type ) == CV_32FC1 );
		idxdata = sampleIdx->data.ptr;
		idxstep = ( sampleIdx->rows == 1 )
				  ? CV_ELEM_SIZE( sampleIdx->type ) : sampleIdx->step;
		l = ( sampleIdx->rows == 1 ) ? sampleIdx->cols : sampleIdx->rows;

		if ( sorteddata != NULL ) {
			filter = (char*) cvAlloc( sizeof( char ) * m );
			memset( (void*) filter, 0, sizeof( char ) * m );
			for ( i = 0; i < l; i++ ) {
				filter[(int) *((float*) (idxdata + i * idxstep))] = (char) 1;
			}
		}
	} else {
		l = m;
	}

	stump = (CvStumpClassifier*) cvAlloc( sizeof( CvStumpClassifier) );

	/* START */
	memset( (void*) stump, 0, sizeof( CvStumpClassifier ) );

	portion = ((CvMTStumpTrainParams*)trainParams)->portion;

	if ( portion < 1 ) {
		/* auto portion */
		portion = n;
#ifdef _OPENMP
		portion /= omp_get_max_threads();
#endif /* _OPENMP */
	}

	stump->eval = cvEvalStumpClassifier;
	stump->tune = NULL;
	stump->save = NULL;
	stump->release = cvReleaseStumpClassifier;

	stump->lerror = FLT_MAX;
	stump->rerror = FLT_MAX;
	stump->left  = 0.0F;
	stump->right = 0.0F;

	compidx = 0;
#ifdef _OPENMP
#pragma omp parallel private(mat, va, lerror, rerror, left, right, threshold, \
                                 optcompidx, sumw, sumwy, sumwyy, t_compidx, t_n, \
                                 ti, tj, tk, t_data, t_cstep, t_sstep, matcstep,  \
                                 matsstep, t_idx)
#endif /* _OPENMP */
	{
		lerror = FLT_MAX;
		rerror = FLT_MAX;
		left  = 0.0F;
		right = 0.0F;
		threshold = 0.0F;
		optcompidx = 0;

		sumw   = FLT_MAX;
		sumwy  = FLT_MAX;
		sumwyy = FLT_MAX;

		t_compidx = 0;
		t_n = 0;

		ti = 0;
		tj = 0;
		tk = 0;

		t_data = NULL;
		t_cstep = 0;
		t_sstep = 0;

		matcstep = 0;
		matsstep = 0;

		t_idx = NULL;

		mat.data.ptr = NULL;

		if ( datan < n ) {
			/* prepare matrix for callback */
			if ( CV_IS_ROW_SAMPLE( flags ) ) {
				mat = cvMat( m, portion, CV_32FC1, 0 );
				matcstep = CV_ELEM_SIZE( mat.type );
				matsstep = mat.step;
			} else {
				mat = cvMat( portion, m, CV_32FC1, 0 );
				matcstep = mat.step;
				matsstep = CV_ELEM_SIZE( mat.type );
			}
			mat.data.ptr = (uchar*) cvAlloc( sizeof( float ) * mat.rows * mat.cols );
		}

		if ( filter != NULL || sortedn < n ) {
			t_idx = (int*) cvAlloc( sizeof( int ) * m );
			if ( sortedn == 0 || filter == NULL ) {
				if ( idxdata != NULL ) {
					for ( ti = 0; ti < l; ti++ ) {
						t_idx[ti] = (int) * ((float*) (idxdata + ti * idxstep));
					}
				} else {
					for ( ti = 0; ti < l; ti++ ) {
						t_idx[ti] = ti;
					}
				}
			}
		}

#ifdef _OPENMP
#pragma omp critical(c_compidx)
#endif /* _OPENMP */
		{
			t_compidx = compidx;
			compidx += portion;
		}
		while ( t_compidx < n ) {
			t_n = portion;
			if ( t_compidx < datan ) {
				t_n = ( t_n < (datan - t_compidx) ) ? t_n : (datan - t_compidx);
				t_data = data;
				t_cstep = cstep;
				t_sstep = sstep;
			} else {
				t_n = ( t_n < (n - t_compidx) ) ? t_n : (n - t_compidx);
				t_cstep = matcstep;
				t_sstep = matsstep;
				t_data = mat.data.ptr - t_compidx * ((size_t) t_cstep );

				/* calculate components */
				((CvMTStumpTrainParams*)trainParams)->getTrainData( &mat,
						sampleIdx, compIdx, t_compidx, t_n,
						((CvMTStumpTrainParams*)trainParams)->userdata );
			}

			if ( sorteddata != NULL ) {
				if ( filter != NULL ) {
					/* have sorted indices and filter */
					switch ( sortedtype ) {
					case CV_16SC1:
						for ( ti = t_compidx; ti < MIN( sortedn, t_compidx + t_n ); ti++ ) {
							tk = 0;
							for ( tj = 0; tj < sortedm; tj++ ) {
								int curidx = (int) ( *((short*) (sorteddata
																 + ti * sortedcstep + tj * sortedsstep)) );
								if ( filter[curidx] != 0 ) {
									t_idx[tk++] = curidx;
								}
							}
							if ( findStumpThreshold_32s[stumperror](
										t_data + ti * t_cstep, t_sstep,
										wdata, wstep, ydata, ystep,
										(uchar*) t_idx, sizeof( int ), tk,
										&lerror, &rerror,
										&threshold, &left, &right,
										&sumw, &sumwy, &sumwyy ) ) {
								optcompidx = ti;
							}
						}
						break;
					case CV_32SC1:
						for ( ti = t_compidx; ti < MIN( sortedn, t_compidx + t_n ); ti++ ) {
							tk = 0;
							for ( tj = 0; tj < sortedm; tj++ ) {
								int curidx = (int) ( *((int*) (sorteddata
															   + ti * sortedcstep + tj * sortedsstep)) );
								if ( filter[curidx] != 0 ) {
									t_idx[tk++] = curidx;
								}
							}
							if ( findStumpThreshold_32s[stumperror](
										t_data + ti * t_cstep, t_sstep,
										wdata, wstep, ydata, ystep,
										(uchar*) t_idx, sizeof( int ), tk,
										&lerror, &rerror,
										&threshold, &left, &right,
										&sumw, &sumwy, &sumwyy ) ) {
								optcompidx = ti;
							}
						}
						break;
					case CV_32FC1:
						for ( ti = t_compidx; ti < MIN( sortedn, t_compidx + t_n ); ti++ ) {
							tk = 0;
							for ( tj = 0; tj < sortedm; tj++ ) {
								int curidx = (int) ( *((float*) (sorteddata
																 + ti * sortedcstep + tj * sortedsstep)) );
								if ( filter[curidx] != 0 ) {
									t_idx[tk++] = curidx;
								}
							}
							if ( findStumpThreshold_32s[stumperror](
										t_data + ti * t_cstep, t_sstep,
										wdata, wstep, ydata, ystep,
										(uchar*) t_idx, sizeof( int ), tk,
										&lerror, &rerror,
										&threshold, &left, &right,
										&sumw, &sumwy, &sumwyy ) ) {
								optcompidx = ti;
							}
						}
						break;
					default:
						assert( 0 );
						break;
					}
				} else {
					/* have sorted indices */
					switch ( sortedtype ) {
					case CV_16SC1:
						for ( ti = t_compidx; ti < MIN( sortedn, t_compidx + t_n ); ti++ ) {
							if ( findStumpThreshold_16s[stumperror](
										t_data + ti * t_cstep, t_sstep,
										wdata, wstep, ydata, ystep,
										sorteddata + ti * sortedcstep, sortedsstep, sortedm,
										&lerror, &rerror,
										&threshold, &left, &right,
										&sumw, &sumwy, &sumwyy ) ) {
								optcompidx = ti;
							}
						}
						break;
					case CV_32SC1:
						for ( ti = t_compidx; ti < MIN( sortedn, t_compidx + t_n ); ti++ ) {
							if ( findStumpThreshold_32s[stumperror](
										t_data + ti * t_cstep, t_sstep,
										wdata, wstep, ydata, ystep,
										sorteddata + ti * sortedcstep, sortedsstep, sortedm,
										&lerror, &rerror,
										&threshold, &left, &right,
										&sumw, &sumwy, &sumwyy ) ) {
								optcompidx = ti;
							}
						}
						break;
					case CV_32FC1:
						for ( ti = t_compidx; ti < MIN( sortedn, t_compidx + t_n ); ti++ ) {
							if ( findStumpThreshold_32f[stumperror](
										t_data + ti * t_cstep, t_sstep,
										wdata, wstep, ydata, ystep,
										sorteddata + ti * sortedcstep, sortedsstep, sortedm,
										&lerror, &rerror,
										&threshold, &left, &right,
										&sumw, &sumwy, &sumwyy ) ) {
								optcompidx = ti;
							}
						}
						break;
					default:
						assert( 0 );
						break;
					}
				}
			}

			ti = MAX( t_compidx, MIN( sortedn, t_compidx + t_n ) );
			for ( ; ti < t_compidx + t_n; ti++ ) {
				va.data = t_data + ti * t_cstep;
				va.step = t_sstep;
				icvSortIndexedValArray_32s( t_idx, l, &va );
				if ( findStumpThreshold_32s[stumperror](
							t_data + ti * t_cstep, t_sstep,
							wdata, wstep, ydata, ystep,
							(uchar*)t_idx, sizeof( int ), l,
							&lerror, &rerror,
							&threshold, &left, &right,
							&sumw, &sumwy, &sumwyy ) ) {
					optcompidx = ti;
				}
			}
#ifdef _OPENMP
#pragma omp critical(c_compidx)
#endif /* _OPENMP */
			{
				t_compidx = compidx;
				compidx += portion;
			}
		} /* while have training data */

		/* get the best classifier */
#ifdef _OPENMP
#pragma omp critical(c_beststump)
#endif /* _OPENMP */
		{
			if ( lerror + rerror < stump->lerror + stump->rerror ) {
				stump->lerror    = lerror;
				stump->rerror    = rerror;
				stump->compidx   = optcompidx;
				stump->threshold = threshold;
				stump->left      = left;
				stump->right     = right;
			}
		}

		/* free allocated memory */
		if ( mat.data.ptr != NULL ) {
			cvFree( &(mat.data.ptr) );
		}
		if ( t_idx != NULL ) {
			cvFree( &t_idx );
		}
	} /* end of parallel region */

	/* END */

	/* free allocated memory */
	if ( filter != NULL ) {
		cvFree( &filter );
	}

	if ( ((CvMTStumpTrainParams*) trainParams)->type == CV_CLASSIFICATION_CLASS ) {
		stump->left = 2.0F * (stump->left >= 0.5F) - 1.0F;
		stump->right = 2.0F * (stump->right >= 0.5F) - 1.0F;
	}

	return (CvClassifier*) stump;
}

CV_BOOST_IMPL
float cvEvalCARTClassifier( CvClassifier* classifier, CvMat* sample ) {
	CV_FUNCNAME( "cvEvalCARTClassifier" );

	int idx = 0;

	__BEGIN__;


	CV_ASSERT( classifier != NULL );
	CV_ASSERT( sample != NULL );
	CV_ASSERT( CV_MAT_TYPE( sample->type ) == CV_32FC1 );
	CV_ASSERT( sample->rows == 1 || sample->cols == 1 );

	if ( sample->rows == 1 ) {
		do {
			if ( (CV_MAT_ELEM( (*sample), float, 0,
							   ((CvCARTClassifier*) classifier)->compidx[idx] )) <
					((CvCARTClassifier*) classifier)->threshold[idx] ) {
				idx = ((CvCARTClassifier*) classifier)->left[idx];
			} else {
				idx = ((CvCARTClassifier*) classifier)->right[idx];
			}
		} while ( idx > 0 );
	} else {
		do {
			if ( (CV_MAT_ELEM( (*sample), float,
							   ((CvCARTClassifier*) classifier)->compidx[idx], 0 )) <
					((CvCARTClassifier*) classifier)->threshold[idx] ) {
				idx = ((CvCARTClassifier*) classifier)->left[idx];
			} else {
				idx = ((CvCARTClassifier*) classifier)->right[idx];
			}
		} while ( idx > 0 );
	}

	__END__;

	return ((CvCARTClassifier*) classifier)->val[-idx];
}

CV_BOOST_IMPL
float cvEvalCARTClassifierIdx( CvClassifier* classifier, CvMat* sample ) {
	CV_FUNCNAME( "cvEvalCARTClassifierIdx" );

	int idx = 0;

	__BEGIN__;


	CV_ASSERT( classifier != NULL );
	CV_ASSERT( sample != NULL );
	CV_ASSERT( CV_MAT_TYPE( sample->type ) == CV_32FC1 );
	CV_ASSERT( sample->rows == 1 || sample->cols == 1 );

	if ( sample->rows == 1 ) {
		do {
			if ( (CV_MAT_ELEM( (*sample), float, 0,
							   ((CvCARTClassifier*) classifier)->compidx[idx] )) <
					((CvCARTClassifier*) classifier)->threshold[idx] ) {
				idx = ((CvCARTClassifier*) classifier)->left[idx];
			} else {
				idx = ((CvCARTClassifier*) classifier)->right[idx];
			}
		} while ( idx > 0 );
	} else {
		do {
			if ( (CV_MAT_ELEM( (*sample), float,
							   ((CvCARTClassifier*) classifier)->compidx[idx], 0 )) <
					((CvCARTClassifier*) classifier)->threshold[idx] ) {
				idx = ((CvCARTClassifier*) classifier)->left[idx];
			} else {
				idx = ((CvCARTClassifier*) classifier)->right[idx];
			}
		} while ( idx > 0 );
	}

	__END__;

	return (float) (-idx);
}

CV_BOOST_IMPL
void cvReleaseCARTClassifier( CvClassifier** classifier ) {
	cvFree( classifier );
	*classifier = NULL;
}

void CV_CDECL icvDefaultSplitIdx_R( int compidx, float threshold,
									CvMat* idx, CvMat** left, CvMat** right,
									void* userdata ) {
	CvMat* trainData = (CvMat*) userdata;
	int i = 0;

	*left = cvCreateMat( 1, trainData->rows, CV_32FC1 );
	*right = cvCreateMat( 1, trainData->rows, CV_32FC1 );
	(*left)->cols = (*right)->cols = 0;
	if ( idx == NULL ) {
		for ( i = 0; i < trainData->rows; i++ ) {
			if ( CV_MAT_ELEM( *trainData, float, i, compidx ) < threshold ) {
				(*left)->data.fl[(*left)->cols++] = (float) i;
			} else {
				(*right)->data.fl[(*right)->cols++] = (float) i;
			}
		}
	} else {
		uchar* idxdata;
		int idxnum;
		int idxstep;
		int index;

		idxdata = idx->data.ptr;
		idxnum = (idx->rows == 1) ? idx->cols : idx->rows;
		idxstep = (idx->rows == 1) ? CV_ELEM_SIZE( idx->type ) : idx->step;
		for ( i = 0; i < idxnum; i++ ) {
			index = (int) * ((float*) (idxdata + i * idxstep));
			if ( CV_MAT_ELEM( *trainData, float, index, compidx ) < threshold ) {
				(*left)->data.fl[(*left)->cols++] = (float) index;
			} else {
				(*right)->data.fl[(*right)->cols++] = (float) index;
			}
		}
	}
}

void CV_CDECL icvDefaultSplitIdx_C( int compidx, float threshold,
									CvMat* idx, CvMat** left, CvMat** right,
									void* userdata ) {
	CvMat* trainData = (CvMat*) userdata;
	int i = 0;

	*left = cvCreateMat( 1, trainData->cols, CV_32FC1 );
	*right = cvCreateMat( 1, trainData->cols, CV_32FC1 );
	(*left)->cols = (*right)->cols = 0;
	if ( idx == NULL ) {
		for ( i = 0; i < trainData->cols; i++ ) {
			if ( CV_MAT_ELEM( *trainData, float, compidx, i ) < threshold ) {
				(*left)->data.fl[(*left)->cols++] = (float) i;
			} else {
				(*right)->data.fl[(*right)->cols++] = (float) i;
			}
		}
	} else {
		uchar* idxdata;
		int idxnum;
		int idxstep;
		int index;

		idxdata = idx->data.ptr;
		idxnum = (idx->rows == 1) ? idx->cols : idx->rows;
		idxstep = (idx->rows == 1) ? CV_ELEM_SIZE( idx->type ) : idx->step;
		for ( i = 0; i < idxnum; i++ ) {
			index = (int) * ((float*) (idxdata + i * idxstep));
			if ( CV_MAT_ELEM( *trainData, float, compidx, index ) < threshold ) {
				(*left)->data.fl[(*left)->cols++] = (float) index;
			} else {
				(*right)->data.fl[(*right)->cols++] = (float) index;
			}
		}
	}
}

/* internal structure used in CART creation */
typedef struct CvCARTNode {
	CvMat* sampleIdx;
	CvStumpClassifier* stump;
	int parent;
	int leftflag;
	float errdrop;
} CvCARTNode;

CV_BOOST_IMPL
CvClassifier* cvCreateCARTClassifier( CvMat* trainData,
									  int flags,
									  CvMat* trainClasses,
									  CvMat* typeMask,
									  CvMat* missedMeasurementsMask,
									  CvMat* compIdx,
									  CvMat* sampleIdx,
									  CvMat* weights,
									  CvClassifierTrainParams* trainParams ) {
	CvCARTClassifier* cart = NULL;
	size_t datasize = 0;
	int count = 0;
	int i = 0;
	int j = 0;

	CvCARTNode* intnode = NULL;
	CvCARTNode* list = NULL;
	int listcount = 0;
	CvMat* lidx = NULL;
	CvMat* ridx = NULL;

	float maxerrdrop = 0.0F;
	int idx = 0;

	void (*splitIdxCallback)( int compidx, float threshold,
							  CvMat * idx, CvMat** left, CvMat** right,
							  void * userdata );
	void* userdata;

	count = ((CvCARTTrainParams*) trainParams)->count;

	assert( count > 0 );

	datasize = sizeof( *cart ) + (sizeof( float ) + 3 * sizeof( int )) * count +
			   sizeof( float ) * (count + 1);

	cart = (CvCARTClassifier*) cvAlloc( datasize );
	memset( cart, 0, datasize );

	cart->count = count;

	cart->eval = cvEvalCARTClassifier;
	cart->save = NULL;
	cart->release = cvReleaseCARTClassifier;

	cart->compidx = (int*) (cart + 1);
	cart->threshold = (float*) (cart->compidx + count);
	cart->left  = (int*) (cart->threshold + count);
	cart->right = (int*) (cart->left + count);
	cart->val = (float*) (cart->right + count);

	datasize = sizeof( CvCARTNode ) * (count + count);
	intnode = (CvCARTNode*) cvAlloc( datasize );
	memset( intnode, 0, datasize );
	list = (CvCARTNode*) (intnode + count);

	splitIdxCallback = ((CvCARTTrainParams*) trainParams)->splitIdx;
	userdata = ((CvCARTTrainParams*) trainParams)->userdata;
	if ( splitIdxCallback == NULL ) {
		splitIdxCallback = ( CV_IS_ROW_SAMPLE( flags ) )
						   ? icvDefaultSplitIdx_R : icvDefaultSplitIdx_C;
		userdata = trainData;
	}

	/* create root of the tree */
	intnode[0].sampleIdx = sampleIdx;
	intnode[0].stump = (CvStumpClassifier*)
					   ((CvCARTTrainParams*) trainParams)->stumpConstructor( trainData, flags,
							   trainClasses, typeMask, missedMeasurementsMask, compIdx, sampleIdx, weights,
							   ((CvCARTTrainParams*) trainParams)->stumpTrainParams );
	cart->left[0] = cart->right[0] = 0;

	/* build tree */
	listcount = 0;
	for ( i = 1; i < count; i++ ) {
		/* split last added node */
		splitIdxCallback( intnode[i-1].stump->compidx, intnode[i-1].stump->threshold,
						  intnode[i-1].sampleIdx, &lidx, &ridx, userdata );

		if ( intnode[i-1].stump->lerror != 0.0F ) {
			list[listcount].sampleIdx = lidx;
			list[listcount].stump = (CvStumpClassifier*)
									((CvCARTTrainParams*) trainParams)->stumpConstructor( trainData, flags,
											trainClasses, typeMask, missedMeasurementsMask, compIdx,
											list[listcount].sampleIdx,
											weights, ((CvCARTTrainParams*) trainParams)->stumpTrainParams );
			list[listcount].errdrop = intnode[i-1].stump->lerror
									  - (list[listcount].stump->lerror + list[listcount].stump->rerror);
			list[listcount].leftflag = 1;
			list[listcount].parent = i - 1;
			listcount++;
		} else {
			cvReleaseMat( &lidx );
		}
		if ( intnode[i-1].stump->rerror != 0.0F ) {
			list[listcount].sampleIdx = ridx;
			list[listcount].stump = (CvStumpClassifier*)
									((CvCARTTrainParams*) trainParams)->stumpConstructor( trainData, flags,
											trainClasses, typeMask, missedMeasurementsMask, compIdx,
											list[listcount].sampleIdx,
											weights, ((CvCARTTrainParams*) trainParams)->stumpTrainParams );
			list[listcount].errdrop = intnode[i-1].stump->rerror
									  - (list[listcount].stump->lerror + list[listcount].stump->rerror);
			list[listcount].leftflag = 0;
			list[listcount].parent = i - 1;
			listcount++;
		} else {
			cvReleaseMat( &ridx );
		}

		if ( listcount == 0 ) { break; }

		/* find the best node to be added to the tree */
		idx = 0;
		maxerrdrop = list[idx].errdrop;
		for ( j = 1; j < listcount; j++ ) {
			if ( list[j].errdrop > maxerrdrop ) {
				idx = j;
				maxerrdrop = list[j].errdrop;
			}
		}
		intnode[i] = list[idx];
		if ( list[idx].leftflag ) {
			cart->left[list[idx].parent] = i;
		} else {
			cart->right[list[idx].parent] = i;
		}
		if ( idx != (listcount - 1) ) {
			list[idx] = list[listcount - 1];
		}
		listcount--;
	}

	/* fill <cart> fields */
	j = 0;
	cart->count = 0;
	for ( i = 0; i < count && (intnode[i].stump != NULL); i++ ) {
		cart->count++;
		cart->compidx[i] = intnode[i].stump->compidx;
		cart->threshold[i] = intnode[i].stump->threshold;

		/* leaves */
		if ( cart->left[i] <= 0 ) {
			cart->left[i] = -j;
			cart->val[j] = intnode[i].stump->left;
			j++;
		}
		if ( cart->right[i] <= 0 ) {
			cart->right[i] = -j;
			cart->val[j] = intnode[i].stump->right;
			j++;
		}
	}

	/* CLEAN UP */
	for ( i = 0; i < count && (intnode[i].stump != NULL); i++ ) {
		intnode[i].stump->release( (CvClassifier**) &(intnode[i].stump) );
		if ( i != 0 ) {
			cvReleaseMat( &(intnode[i].sampleIdx) );
		}
	}
	for ( i = 0; i < listcount; i++ ) {
		list[i].stump->release( (CvClassifier**) &(list[i].stump) );
		cvReleaseMat( &(list[i].sampleIdx) );
	}

	cvFree( &intnode );

	return (CvClassifier*) cart;
}

/****************************************************************************************\
*                                        Boosting                                        *
\****************************************************************************************/

typedef struct CvBoostTrainer {
	CvBoostType type;
	int count;             /* (idx) ? number_of_indices : number_of_samples */
	int* idx;
	float* F;
} CvBoostTrainer;

/*
 * cvBoostStartTraining, cvBoostNextWeakClassifier, cvBoostEndTraining
 *
 * These functions perform training of 2-class boosting classifier
 * using ANY appropriate weak classifier
 */

CV_BOOST_IMPL
CvBoostTrainer* icvBoostStartTraining( CvMat* trainClasses,
									   CvMat* weakTrainVals,
									   CvMat* /*weights*/,
									   CvMat* sampleIdx,
									   CvBoostType type ) {
	uchar* ydata;
	int ystep;
	int m;
	uchar* traindata;
	int trainstep;
	int trainnum;
	int i;
	int idx;

	size_t datasize;
	CvBoostTrainer* ptr;

	int idxnum;
	int idxstep;
	uchar* idxdata;

	assert( trainClasses != NULL );
	assert( CV_MAT_TYPE( trainClasses->type ) == CV_32FC1 );
	assert( weakTrainVals != NULL );
	assert( CV_MAT_TYPE( weakTrainVals->type ) == CV_32FC1 );

	CV_MAT2VEC( *trainClasses, ydata, ystep, m );
	CV_MAT2VEC( *weakTrainVals, traindata, trainstep, trainnum );

	assert( m == trainnum );

	idxnum = 0;
	idxstep = 0;
	idxdata = NULL;
	if ( sampleIdx ) {
		CV_MAT2VEC( *sampleIdx, idxdata, idxstep, idxnum );
	}

	datasize = sizeof( *ptr ) + sizeof( *ptr->idx ) * idxnum;
	ptr = (CvBoostTrainer*) cvAlloc( datasize );
	memset( ptr, 0, datasize );
	ptr->F = NULL;
	ptr->idx = NULL;

	ptr->count = m;
	ptr->type = type;

	if ( idxnum > 0 ) {
		CvScalar s;

		ptr->idx = (int*) (ptr + 1);
		ptr->count = idxnum;
		for ( i = 0; i < ptr->count; i++ ) {
			cvRawDataToScalar( idxdata + i * idxstep, CV_MAT_TYPE( sampleIdx->type ), &s );
			ptr->idx[i] = (int) s.val[0];
		}
	}
	for ( i = 0; i < ptr->count; i++ ) {
		idx = (ptr->idx) ? ptr->idx[i] : i;

		*((float*) (traindata + idx * trainstep)) =
			2.0F * (*((float*) (ydata + idx * ystep))) - 1.0F;
	}

	return ptr;
}

/*
 *
 * Discrete AdaBoost functions
 *
 */
CV_BOOST_IMPL
float icvBoostNextWeakClassifierDAB( CvMat* weakEvalVals,
									 CvMat* trainClasses,
									 CvMat* /*weakTrainVals*/,
									 CvMat* weights,
									 CvBoostTrainer* trainer ) {
	uchar* evaldata;
	int evalstep;
	int m;
	uchar* ydata;
	int ystep;
	int ynum;
	uchar* wdata;
	int wstep;
	int wnum;

	float sumw;
	float err;
	int i;
	int idx;

	CV_Assert( weakEvalVals != NULL );
	CV_Assert( CV_MAT_TYPE( weakEvalVals->type ) == CV_32FC1 );
	CV_Assert( trainClasses != NULL );
	CV_Assert( CV_MAT_TYPE( trainClasses->type ) == CV_32FC1 );
	CV_Assert( weights != NULL );
	CV_Assert( CV_MAT_TYPE( weights ->type ) == CV_32FC1 );

	CV_MAT2VEC( *weakEvalVals, evaldata, evalstep, m );
	CV_MAT2VEC( *trainClasses, ydata, ystep, ynum );
	CV_MAT2VEC( *weights, wdata, wstep, wnum );

	assert( m == ynum );
	assert( m == wnum );

	sumw = 0.0F;
	err = 0.0F;
	for ( i = 0; i < trainer->count; i++ ) {
		idx = (trainer->idx) ? trainer->idx[i] : i;

		sumw += *((float*) (wdata + idx * wstep));
		err += (*((float*) (wdata + idx * wstep))) *
			   ( (*((float*) (evaldata + idx * evalstep))) !=
				 2.0F * (*((float*) (ydata + idx * ystep))) - 1.0F );
	}
	err /= sumw;
	err = -cvLogRatio( err );

	for ( i = 0; i < trainer->count; i++ ) {
		idx = (trainer->idx) ? trainer->idx[i] : i;

		*((float*) (wdata + idx * wstep)) *= expf( err *
											 ((*((float*) (evaldata + idx * evalstep))) !=
											  2.0F * (*((float*) (ydata + idx * ystep))) - 1.0F) );
		sumw += *((float*) (wdata + idx * wstep));
	}
	for ( i = 0; i < trainer->count; i++ ) {
		idx = (trainer->idx) ? trainer->idx[i] : i;

		*((float*) (wdata + idx * wstep)) /= sumw;
	}

	return err;
}

/*
 *
 * Real AdaBoost functions
 *
 */
CV_BOOST_IMPL
float icvBoostNextWeakClassifierRAB( CvMat* weakEvalVals,
									 CvMat* trainClasses,
									 CvMat* /*weakTrainVals*/,
									 CvMat* weights,
									 CvBoostTrainer* trainer ) {
	uchar* evaldata;
	int evalstep;
	int m;
	uchar* ydata;
	int ystep;
	int ynum;
	uchar* wdata;
	int wstep;
	int wnum;

	float sumw;
	int i, idx;

	CV_Assert( weakEvalVals != NULL );
	CV_Assert( CV_MAT_TYPE( weakEvalVals->type ) == CV_32FC1 );
	CV_Assert( trainClasses != NULL );
	CV_Assert( CV_MAT_TYPE( trainClasses->type ) == CV_32FC1 );
	CV_Assert( weights != NULL );
	CV_Assert( CV_MAT_TYPE( weights ->type ) == CV_32FC1 );

	CV_MAT2VEC( *weakEvalVals, evaldata, evalstep, m );
	CV_MAT2VEC( *trainClasses, ydata, ystep, ynum );
	CV_MAT2VEC( *weights, wdata, wstep, wnum );

	CV_Assert( m == ynum );
	CV_Assert( m == wnum );


	sumw = 0.0F;
	for ( i = 0; i < trainer->count; i++ ) {
		idx = (trainer->idx) ? trainer->idx[i] : i;

		*((float*) (wdata + idx * wstep)) *= expf( (-(*((float*) (ydata + idx * ystep))) + 0.5F)
											 * cvLogRatio( *((float*) (evaldata + idx * evalstep)) ) );
		sumw += *((float*) (wdata + idx * wstep));
	}
	for ( i = 0; i < trainer->count; i++ ) {
		idx = (trainer->idx) ? trainer->idx[i] : i;

		*((float*) (wdata + idx * wstep)) /= sumw;
	}

	return 1.0F;
}

/*
 *
 * LogitBoost functions
 *
 */
#define CV_LB_PROB_THRESH      0.01F
#define CV_LB_WEIGHT_THRESHOLD 0.0001F

CV_BOOST_IMPL
void icvResponsesAndWeightsLB( int num, uchar* wdata, int wstep,
							   uchar* ydata, int ystep,
							   uchar* fdata, int fstep,
							   uchar* traindata, int trainstep,
							   int* indices ) {
	int i, idx;
	float p;

	for ( i = 0; i < num; i++ ) {
		idx = (indices) ? indices[i] : i;

		p = 1.0F / (1.0F + expf( -(*((float*) (fdata + idx * fstep)))) );
		*((float*) (wdata + idx * wstep)) = MAX( p * (1.0F - p), CV_LB_WEIGHT_THRESHOLD );
		if ( *((float*) (ydata + idx * ystep)) == 1.0F ) {
			*((float*) (traindata + idx * trainstep)) =
				1.0F / (MAX( p, CV_LB_PROB_THRESH ));
		} else {
			*((float*) (traindata + idx * trainstep)) =
				-1.0F / (MAX( 1.0F - p, CV_LB_PROB_THRESH ));
		}
	}
}

CV_BOOST_IMPL
CvBoostTrainer* icvBoostStartTrainingLB( CvMat* trainClasses,
		CvMat* weakTrainVals,
		CvMat* weights,
		CvMat* sampleIdx,
		CvBoostType type ) {
	size_t datasize;
	CvBoostTrainer* ptr;

	uchar* ydata;
	int ystep;
	int m;
	uchar* traindata;
	int trainstep;
	int trainnum;
	uchar* wdata;
	int wstep;
	int wnum;
	int i;

	int idxnum;
	int idxstep;
	uchar* idxdata;

	assert( trainClasses != NULL );
	assert( CV_MAT_TYPE( trainClasses->type ) == CV_32FC1 );
	assert( weakTrainVals != NULL );
	assert( CV_MAT_TYPE( weakTrainVals->type ) == CV_32FC1 );
	assert( weights != NULL );
	assert( CV_MAT_TYPE( weights->type ) == CV_32FC1 );

	CV_MAT2VEC( *trainClasses, ydata, ystep, m );
	CV_MAT2VEC( *weakTrainVals, traindata, trainstep, trainnum );
	CV_MAT2VEC( *weights, wdata, wstep, wnum );

	assert( m == trainnum );
	assert( m == wnum );


	idxnum = 0;
	idxstep = 0;
	idxdata = NULL;
	if ( sampleIdx ) {
		CV_MAT2VEC( *sampleIdx, idxdata, idxstep, idxnum );
	}

	datasize = sizeof( *ptr ) + sizeof( *ptr->F ) * m + sizeof( *ptr->idx ) * idxnum;
	ptr = (CvBoostTrainer*) cvAlloc( datasize );
	memset( ptr, 0, datasize );
	ptr->F = (float*) (ptr + 1);
	ptr->idx = NULL;

	ptr->count = m;
	ptr->type = type;

	if ( idxnum > 0 ) {
		CvScalar s;

		ptr->idx = (int*) (ptr->F + m);
		ptr->count = idxnum;
		for ( i = 0; i < ptr->count; i++ ) {
			cvRawDataToScalar( idxdata + i * idxstep, CV_MAT_TYPE( sampleIdx->type ), &s );
			ptr->idx[i] = (int) s.val[0];
		}
	}

	for ( i = 0; i < m; i++ ) {
		ptr->F[i] = 0.0F;
	}

	icvResponsesAndWeightsLB( ptr->count, wdata, wstep, ydata, ystep,
							  (uchar*) ptr->F, sizeof( *ptr->F ),
							  traindata, trainstep, ptr->idx );

	return ptr;
}

CV_BOOST_IMPL
float icvBoostNextWeakClassifierLB( CvMat* weakEvalVals,
									CvMat* trainClasses,
									CvMat* weakTrainVals,
									CvMat* weights,
									CvBoostTrainer* trainer ) {
	uchar* evaldata;
	int evalstep;
	int m;
	uchar* ydata;
	int ystep;
	int ynum;
	uchar* traindata;
	int trainstep;
	int trainnum;
	uchar* wdata;
	int wstep;
	int wnum;
	int i, idx;

	assert( weakEvalVals != NULL );
	assert( CV_MAT_TYPE( weakEvalVals->type ) == CV_32FC1 );
	assert( trainClasses != NULL );
	assert( CV_MAT_TYPE( trainClasses->type ) == CV_32FC1 );
	assert( weakTrainVals != NULL );
	assert( CV_MAT_TYPE( weakTrainVals->type ) == CV_32FC1 );
	assert( weights != NULL );
	assert( CV_MAT_TYPE( weights ->type ) == CV_32FC1 );

	CV_MAT2VEC( *weakEvalVals, evaldata, evalstep, m );
	CV_MAT2VEC( *trainClasses, ydata, ystep, ynum );
	CV_MAT2VEC( *weakTrainVals, traindata, trainstep, trainnum );
	CV_MAT2VEC( *weights, wdata, wstep, wnum );

	assert( m == ynum );
	assert( m == wnum );
	assert( m == trainnum );
	//assert( m == trainer->count );

	for ( i = 0; i < trainer->count; i++ ) {
		idx = (trainer->idx) ? trainer->idx[i] : i;

		trainer->F[idx] += *((float*) (evaldata + idx * evalstep));
	}

	icvResponsesAndWeightsLB( trainer->count, wdata, wstep, ydata, ystep,
							  (uchar*) trainer->F, sizeof( *trainer->F ),
							  traindata, trainstep, trainer->idx );

	return 1.0F;
}

/*
 *
 * Gentle AdaBoost
 *
 */
CV_BOOST_IMPL
float icvBoostNextWeakClassifierGAB( CvMat* weakEvalVals,
									 CvMat* trainClasses,
									 CvMat* /*weakTrainVals*/,
									 CvMat* weights,
									 CvBoostTrainer* trainer ) {
	uchar* evaldata;
	int evalstep;
	int m;
	uchar* ydata;
	int ystep;
	int ynum;
	uchar* wdata;
	int wstep;
	int wnum;

	int i, idx;
	float sumw;

	CV_Assert( weakEvalVals != NULL );
	CV_Assert( CV_MAT_TYPE( weakEvalVals->type ) == CV_32FC1 );
	CV_Assert( trainClasses != NULL );
	CV_Assert( CV_MAT_TYPE( trainClasses->type ) == CV_32FC1 );
	CV_Assert( weights != NULL );
	CV_Assert( CV_MAT_TYPE( weights->type ) == CV_32FC1 );

	CV_MAT2VEC( *weakEvalVals, evaldata, evalstep, m );
	CV_MAT2VEC( *trainClasses, ydata, ystep, ynum );
	CV_MAT2VEC( *weights, wdata, wstep, wnum );

	assert( m == ynum );
	assert( m == wnum );

	sumw = 0.0F;
	for ( i = 0; i < trainer->count; i++ ) {
		idx = (trainer->idx) ? trainer->idx[i] : i;

		*((float*) (wdata + idx * wstep)) *=
			expf( -(*((float*) (evaldata + idx * evalstep)))
				  * ( 2.0F * (*((float*) (ydata + idx * ystep))) - 1.0F ) );
		sumw += *((float*) (wdata + idx * wstep));
	}

	for ( i = 0; i < trainer->count; i++ ) {
		idx = (trainer->idx) ? trainer->idx[i] : i;

		*((float*) (wdata + idx * wstep)) /= sumw;
	}

	return 1.0F;
}

typedef CvBoostTrainer* (*CvBoostStartTraining)( CvMat* trainClasses,
		CvMat* weakTrainVals,
		CvMat* weights,
		CvMat* sampleIdx,
		CvBoostType type );

typedef float (*CvBoostNextWeakClassifier)( CvMat* weakEvalVals,
		CvMat* trainClasses,
		CvMat* weakTrainVals,
		CvMat* weights,
		CvBoostTrainer* data );

CvBoostStartTraining startTraining[4] = {
	icvBoostStartTraining,
	icvBoostStartTraining,
	icvBoostStartTrainingLB,
	icvBoostStartTraining
};

CvBoostNextWeakClassifier nextWeakClassifier[4] = {
	icvBoostNextWeakClassifierDAB,
	icvBoostNextWeakClassifierRAB,
	icvBoostNextWeakClassifierLB,
	icvBoostNextWeakClassifierGAB
};

/*
 *
 * Dispatchers
 *
 */
CV_BOOST_IMPL
CvBoostTrainer* cvBoostStartTraining( CvMat* trainClasses,
									  CvMat* weakTrainVals,
									  CvMat* weights,
									  CvMat* sampleIdx,
									  CvBoostType type ) {
	return startTraining[type]( trainClasses, weakTrainVals, weights, sampleIdx, type );
}

CV_BOOST_IMPL
void cvBoostEndTraining( CvBoostTrainer** trainer ) {
	cvFree( trainer );
	*trainer = NULL;
}

CV_BOOST_IMPL
float cvBoostNextWeakClassifier( CvMat* weakEvalVals,
								 CvMat* trainClasses,
								 CvMat* weakTrainVals,
								 CvMat* weights,
								 CvBoostTrainer* trainer ) {
	return nextWeakClassifier[trainer->type]( weakEvalVals, trainClasses,
			weakTrainVals, weights, trainer    );
}

/****************************************************************************************\
*                                    Boosted tree models                                 *
\****************************************************************************************/

typedef struct CvBtTrainer {
	/* {{ external */
	CvMat* trainData;
	int flags;

	CvMat* trainClasses;
	int m;
	uchar* ydata;
	int ystep;

	CvMat* sampleIdx;
	int numsamples;

	float param[2];
	CvBoostType type;
	int numclasses;
	/* }} external */

	CvMTStumpTrainParams stumpParams;
	CvCARTTrainParams  cartParams;

	float* f;          /* F_(m-1) */
	CvMat* y;          /* yhat    */
	CvMat* weights;
	CvBoostTrainer* boosttrainer;
} CvBtTrainer;

/*
 * cvBtStart, cvBtNext, cvBtEnd
 *
 * These functions perform iterative training of
 * 2-class (CV_DABCLASS - CV_GABCLASS, CV_L2CLASS), K-class (CV_LKCLASS) classifier
 * or fit regression model (CV_LSREG, CV_LADREG, CV_MREG)
 * using decision tree as a weak classifier.
 */

typedef void (*CvZeroApproxFunc)( float* approx, CvBtTrainer* trainer );

/* Mean zero approximation */
void icvZeroApproxMean( float* approx, CvBtTrainer* trainer ) {
	int i;
	int idx;

	approx[0] = 0.0F;
	for ( i = 0; i < trainer->numsamples; i++ ) {
		idx = icvGetIdxAt( trainer->sampleIdx, i );
		approx[0] += *((float*) (trainer->ydata + idx * trainer->ystep));
	}
	approx[0] /= (float) trainer->numsamples;
}

/*
 * Median zero approximation
 */
void icvZeroApproxMed( float* approx, CvBtTrainer* trainer ) {
	int i;
	int idx;

	for ( i = 0; i < trainer->numsamples; i++ ) {
		idx = icvGetIdxAt( trainer->sampleIdx, i );
		trainer->f[i] = *((float*) (trainer->ydata + idx * trainer->ystep));
	}

	icvSort_32f( trainer->f, trainer->numsamples, 0 );
	approx[0] = trainer->f[trainer->numsamples / 2];
}

/*
 * 0.5 * log( mean(y) / (1 - mean(y)) ) where y in {0, 1}
 */
void icvZeroApproxLog( float* approx, CvBtTrainer* trainer ) {
	float y_mean;

	icvZeroApproxMean( &y_mean, trainer );
	approx[0] = 0.5F * cvLogRatio( y_mean );
}

/*
 * 0 zero approximation
 */
void icvZeroApprox0( float* approx, CvBtTrainer* trainer ) {
	int i;

	for ( i = 0; i < trainer->numclasses; i++ ) {
		approx[i] = 0.0F;
	}
}

static CvZeroApproxFunc icvZeroApproxFunc[] = {
	icvZeroApprox0,    /* CV_DABCLASS */
	icvZeroApprox0,    /* CV_RABCLASS */
	icvZeroApprox0,    /* CV_LBCLASS  */
	icvZeroApprox0,    /* CV_GABCLASS */
	icvZeroApproxLog,  /* CV_L2CLASS  */
	icvZeroApprox0,    /* CV_LKCLASS  */
	icvZeroApproxMean, /* CV_LSREG    */
	icvZeroApproxMed,  /* CV_LADREG   */
	icvZeroApproxMed,  /* CV_MREG     */
};

CV_BOOST_IMPL
void cvBtNext( CvCARTClassifier** trees, CvBtTrainer* trainer );

CV_BOOST_IMPL
CvBtTrainer* cvBtStart( CvCARTClassifier** trees,
						CvMat* trainData,
						int flags,
						CvMat* trainClasses,
						CvMat* sampleIdx,
						int numsplits,
						CvBoostType type,
						int numclasses,
						float* param ) {
	CvBtTrainer* ptr = 0;

	CV_FUNCNAME( "cvBtStart" );

	__BEGIN__;

	size_t data_size;
	float* zero_approx;
	int m;
	int i, j;

	if ( trees == NULL ) {
		CV_ERROR( CV_StsNullPtr, "Invalid trees parameter" );
	}

	if ( type < CV_DABCLASS || type > CV_MREG ) {
		CV_ERROR( CV_StsUnsupportedFormat, "Unsupported type parameter" );
	}
	if ( type == CV_LKCLASS ) {
		CV_ASSERT( numclasses >= 2 );
	} else {
		numclasses = 1;
	}

	m = MAX( trainClasses->rows, trainClasses->cols );
	ptr = NULL;
	data_size = sizeof( *ptr );
	if ( type > CV_GABCLASS ) {
		data_size += m * numclasses * sizeof( *(ptr->f) );
	}
	CV_CALL( ptr = (CvBtTrainer*) cvAlloc( data_size ) );
	memset( ptr, 0, data_size );
	ptr->f = (float*) (ptr + 1);

	ptr->trainData = trainData;
	ptr->flags = flags;
	ptr->trainClasses = trainClasses;
	CV_MAT2VEC( *trainClasses, ptr->ydata, ptr->ystep, ptr->m );

	memset( &(ptr->cartParams), 0, sizeof( ptr->cartParams ) );
	memset( &(ptr->stumpParams), 0, sizeof( ptr->stumpParams ) );

	switch ( type ) {
	case CV_DABCLASS:
		ptr->stumpParams.error = CV_MISCLASSIFICATION;
		ptr->stumpParams.type  = CV_CLASSIFICATION_CLASS;
		break;
	case CV_RABCLASS:
		ptr->stumpParams.error = CV_GINI;
		ptr->stumpParams.type  = CV_CLASSIFICATION;
		break;
	default:
		ptr->stumpParams.error = CV_SQUARE;
		ptr->stumpParams.type  = CV_REGRESSION;
	}
	ptr->cartParams.count = numsplits;
	ptr->cartParams.stumpTrainParams = (CvClassifierTrainParams*) & (ptr->stumpParams);
	ptr->cartParams.stumpConstructor = cvCreateMTStumpClassifier;

	ptr->param[0] = param[0];
	ptr->param[1] = param[1];
	ptr->type = type;
	ptr->numclasses = numclasses;

	CV_CALL( ptr->y = cvCreateMat( 1, m, CV_32FC1 ) );
	ptr->sampleIdx = sampleIdx;
	ptr->numsamples = ( sampleIdx == NULL ) ? ptr->m
					  : MAX( sampleIdx->rows, sampleIdx->cols );

	ptr->weights = cvCreateMat( 1, m, CV_32FC1 );
	cvSet( ptr->weights, cvScalar( 1.0 ) );

	if ( type <= CV_GABCLASS ) {
		ptr->boosttrainer = cvBoostStartTraining( ptr->trainClasses, ptr->y,
							ptr->weights, NULL, type );

		CV_CALL( cvBtNext( trees, ptr ) );
	} else {
		data_size = sizeof( *zero_approx ) * numclasses;
		CV_CALL( zero_approx = (float*) cvAlloc( data_size ) );
		icvZeroApproxFunc[type]( zero_approx, ptr );
		for ( i = 0; i < m; i++ ) {
			for ( j = 0; j < numclasses; j++ ) {
				ptr->f[i* numclasses + j] = zero_approx[j];
			}
		}

		CV_CALL( cvBtNext( trees, ptr ) );

		for ( i = 0; i < numclasses; i++ ) {
			for ( j = 0; j <= trees[i]->count; j++ ) {
				trees[i]->val[j] += zero_approx[i];
			}
		}
		CV_CALL( cvFree( &zero_approx ) );
	}

	__END__;

	return ptr;
}

void icvBtNext_LSREG( CvCARTClassifier** trees, CvBtTrainer* trainer ) {
	int i;

	/* yhat_i = y_i - F_(m-1)(x_i) */
	for ( i = 0; i < trainer->m; i++ ) {
		trainer->y->data.fl[i] =
			*((float*) (trainer->ydata + i * trainer->ystep)) - trainer->f[i];
	}

	trees[0] = (CvCARTClassifier*) cvCreateCARTClassifier( trainer->trainData,
			   trainer->flags,
			   trainer->y, NULL, NULL, NULL, trainer->sampleIdx, trainer->weights,
			   (CvClassifierTrainParams*) &trainer->cartParams );
}


void icvBtNext_LADREG( CvCARTClassifier** trees, CvBtTrainer* trainer ) {
	CvCARTClassifier* ptr;
	int i, j;
	CvMat sample;
	int sample_step;
	uchar* sample_data;
	int index;

	int data_size;
	int* idx;
	float* resp;
	int respnum;
	float val;

	data_size = trainer->m * sizeof( *idx );
	idx = (int*) cvAlloc( data_size );
	data_size = trainer->m * sizeof( *resp );
	resp = (float*) cvAlloc( data_size );

	/* yhat_i = sign(y_i - F_(m-1)(x_i)) */
	for ( i = 0; i < trainer->numsamples; i++ ) {
		index = icvGetIdxAt( trainer->sampleIdx, i );
		trainer->y->data.fl[index] = (float)
									 CV_SIGN( *((float*) (trainer->ydata + index * trainer->ystep))
											  - trainer->f[index] );
	}

	ptr = (CvCARTClassifier*) cvCreateCARTClassifier( trainer->trainData, trainer->flags,
			trainer->y, NULL, NULL, NULL, trainer->sampleIdx, trainer->weights,
			(CvClassifierTrainParams*) &trainer->cartParams );

	CV_GET_SAMPLE( *trainer->trainData, trainer->flags, 0, sample );
	CV_GET_SAMPLE_STEP( *trainer->trainData, trainer->flags, sample_step );
	sample_data = sample.data.ptr;
	for ( i = 0; i < trainer->numsamples; i++ ) {
		index = icvGetIdxAt( trainer->sampleIdx, i );
		sample.data.ptr = sample_data + index * sample_step;
		idx[index] = (int) cvEvalCARTClassifierIdx( (CvClassifier*) ptr, &sample );
	}
	for ( j = 0; j <= ptr->count; j++ ) {
		respnum = 0;
		for ( i = 0; i < trainer->numsamples; i++ ) {
			index = icvGetIdxAt( trainer->sampleIdx, i );
			if ( idx[index] == j ) {
				resp[respnum++] = *((float*) (trainer->ydata + index * trainer->ystep))
								  - trainer->f[index];
			}
		}
		if ( respnum > 0 ) {
			icvSort_32f( resp, respnum, 0 );
			val = resp[respnum / 2];
		} else {
			val = 0.0F;
		}
		ptr->val[j] = val;
	}

	cvFree( &idx );
	cvFree( &resp );

	trees[0] = ptr;
}


void icvBtNext_MREG( CvCARTClassifier** trees, CvBtTrainer* trainer ) {
	CvCARTClassifier* ptr;
	int i, j;
	CvMat sample;
	int sample_step;
	uchar* sample_data;

	int data_size;
	int* idx;
	float* resid;
	float* resp;
	int respnum;
	float rhat;
	float val;
	float delta;
	int index;

	data_size = trainer->m * sizeof( *idx );
	idx = (int*) cvAlloc( data_size );
	data_size = trainer->m * sizeof( *resp );
	resp = (float*) cvAlloc( data_size );
	data_size = trainer->m * sizeof( *resid );
	resid = (float*) cvAlloc( data_size );

	/* resid_i = (y_i - F_(m-1)(x_i)) */
	for ( i = 0; i < trainer->numsamples; i++ ) {
		index = icvGetIdxAt( trainer->sampleIdx, i );
		resid[index] = *((float*) (trainer->ydata + index * trainer->ystep))
					   - trainer->f[index];
		/* for delta */
		resp[i] = (float) fabs( resid[index] );
	}

	/* delta = quantile_alpha{abs(resid_i)} */
	icvSort_32f( resp, trainer->numsamples, 0 );
	delta = resp[(int)(trainer->param[1] * (trainer->numsamples - 1))];

	/* yhat_i */
	for ( i = 0; i < trainer->numsamples; i++ ) {
		index = icvGetIdxAt( trainer->sampleIdx, i );
		trainer->y->data.fl[index] = MIN( delta, ((float) fabs( resid[index] )) ) *
									 CV_SIGN( resid[index] );
	}

	ptr = (CvCARTClassifier*) cvCreateCARTClassifier( trainer->trainData, trainer->flags,
			trainer->y, NULL, NULL, NULL, trainer->sampleIdx, trainer->weights,
			(CvClassifierTrainParams*) &trainer->cartParams );

	CV_GET_SAMPLE( *trainer->trainData, trainer->flags, 0, sample );
	CV_GET_SAMPLE_STEP( *trainer->trainData, trainer->flags, sample_step );
	sample_data = sample.data.ptr;
	for ( i = 0; i < trainer->numsamples; i++ ) {
		index = icvGetIdxAt( trainer->sampleIdx, i );
		sample.data.ptr = sample_data + index * sample_step;
		idx[index] = (int) cvEvalCARTClassifierIdx( (CvClassifier*) ptr, &sample );
	}
	for ( j = 0; j <= ptr->count; j++ ) {
		respnum = 0;

		for ( i = 0; i < trainer->numsamples; i++ ) {
			index = icvGetIdxAt( trainer->sampleIdx, i );
			if ( idx[index] == j ) {
				resp[respnum++] = *((float*) (trainer->ydata + index * trainer->ystep))
								  - trainer->f[index];
			}
		}
		if ( respnum > 0 ) {
			/* rhat = median(y_i - F_(m-1)(x_i)) */
			icvSort_32f( resp, respnum, 0 );
			rhat = resp[respnum / 2];

			/* val = sum{sign(r_i - rhat_i) * min(delta, abs(r_i - rhat_i)}
			 * r_i = y_i - F_(m-1)(x_i)
			 */
			val = 0.0F;
			for ( i = 0; i < respnum; i++ ) {
				val += CV_SIGN( resp[i] - rhat )
					   * MIN( delta, (float) fabs( resp[i] - rhat ) );
			}

			val = rhat + val / (float) respnum;
		} else {
			val = 0.0F;
		}

		ptr->val[j] = val;

	}

	cvFree( &resid );
	cvFree( &resp );
	cvFree( &idx );

	trees[0] = ptr;
}

//#define CV_VAL_MAX 1e304

//#define CV_LOG_VAL_MAX 700.0

#define CV_VAL_MAX 1e+8

#define CV_LOG_VAL_MAX 18.0

void icvBtNext_L2CLASS( CvCARTClassifier** trees, CvBtTrainer* trainer ) {
	CvCARTClassifier* ptr;
	int i, j;
	CvMat sample;
	int sample_step;
	uchar* sample_data;

	int data_size;
	int* idx;
	int respnum;
	float val;
	double val_f;

	float sum_weights;
	float* weights;
	float* sorted_weights;
	CvMat* trimmed_idx;
	CvMat* sample_idx;
	int index;
	int trimmed_num;

	data_size = trainer->m * sizeof( *idx );
	idx = (int*) cvAlloc( data_size );

	data_size = trainer->m * sizeof( *weights );
	weights = (float*) cvAlloc( data_size );
	data_size = trainer->m * sizeof( *sorted_weights );
	sorted_weights = (float*) cvAlloc( data_size );

	/* yhat_i = (4 * y_i - 2) / ( 1 + exp( (4 * y_i - 2) * F_(m-1)(x_i) ) ).
	 *   y_i in {0, 1}
	 */
	sum_weights = 0.0F;
	for ( i = 0; i < trainer->numsamples; i++ ) {
		index = icvGetIdxAt( trainer->sampleIdx, i );
		val = 4.0F * (*((float*) (trainer->ydata + index * trainer->ystep))) - 2.0F;
		val_f = val * trainer->f[index];
		val_f = ( val_f < CV_LOG_VAL_MAX ) ? exp( val_f ) : CV_LOG_VAL_MAX;
		val = (float) ( (double) val / ( 1.0 + val_f ) );
		trainer->y->data.fl[index] = val;
		val = (float) fabs( val );
		weights[index] = val * (2.0F - val);
		sorted_weights[i] = weights[index];
		sum_weights += sorted_weights[i];
	}

	trimmed_idx = NULL;
	sample_idx = trainer->sampleIdx;
	trimmed_num = trainer->numsamples;
	if ( trainer->param[1] < 1.0F ) {
		/* perform weight trimming */

		float threshold;
		int count;

		icvSort_32f( sorted_weights, trainer->numsamples, 0 );

		sum_weights *= (1.0F - trainer->param[1]);

		i = -1;
		do { sum_weights -= sorted_weights[++i]; }
		while ( sum_weights > 0.0F && i < (trainer->numsamples - 1) );

		threshold = sorted_weights[i];

		while ( i > 0 && sorted_weights[i-1] == threshold ) { i--; }

		if ( i > 0 ) {
			trimmed_num = trainer->numsamples - i;
			trimmed_idx = cvCreateMat( 1, trimmed_num, CV_32FC1 );
			count = 0;
			for ( i = 0; i < trainer->numsamples; i++ ) {
				index = icvGetIdxAt( trainer->sampleIdx, i );
				if ( weights[index] >= threshold ) {
					CV_MAT_ELEM( *trimmed_idx, float, 0, count ) = (float) index;
					count++;
				}
			}

			assert( count == trimmed_num );

			sample_idx = trimmed_idx;

			printf( "Used samples %%: %g\n",
					(float) trimmed_num / (float) trainer->numsamples * 100.0F );
		}
	}

	ptr = (CvCARTClassifier*) cvCreateCARTClassifier( trainer->trainData, trainer->flags,
			trainer->y, NULL, NULL, NULL, sample_idx, trainer->weights,
			(CvClassifierTrainParams*) &trainer->cartParams );

	CV_GET_SAMPLE( *trainer->trainData, trainer->flags, 0, sample );
	CV_GET_SAMPLE_STEP( *trainer->trainData, trainer->flags, sample_step );
	sample_data = sample.data.ptr;
	for ( i = 0; i < trimmed_num; i++ ) {
		index = icvGetIdxAt( sample_idx, i );
		sample.data.ptr = sample_data + index * sample_step;
		idx[index] = (int) cvEvalCARTClassifierIdx( (CvClassifier*) ptr, &sample );
	}
	for ( j = 0; j <= ptr->count; j++ ) {
		respnum = 0;
		val = 0.0F;
		sum_weights = 0.0F;
		for ( i = 0; i < trimmed_num; i++ ) {
			index = icvGetIdxAt( sample_idx, i );
			if ( idx[index] == j ) {
				val += trainer->y->data.fl[index];
				sum_weights += weights[index];
				respnum++;
			}
		}
		if ( sum_weights > 0.0F ) {
			val /= sum_weights;
		} else {
			val = 0.0F;
		}
		ptr->val[j] = val;
	}

	if ( trimmed_idx != NULL ) { cvReleaseMat( &trimmed_idx ); }
	cvFree( &sorted_weights );
	cvFree( &weights );
	cvFree( &idx );

	trees[0] = ptr;
}

void icvBtNext_LKCLASS( CvCARTClassifier** trees, CvBtTrainer* trainer ) {
	int i, j, k, kk, num;
	CvMat sample;
	int sample_step;
	uchar* sample_data;

	int data_size;
	int* idx;
	int respnum;
	float val;

	float sum_weights;
	float* weights;
	float* sorted_weights;
	CvMat* trimmed_idx;
	CvMat* sample_idx;
	int index;
	int trimmed_num;
	double sum_exp_f;
	double exp_f;
	double f_k;

	data_size = trainer->m * sizeof( *idx );
	idx = (int*) cvAlloc( data_size );
	data_size = trainer->m * sizeof( *weights );
	weights = (float*) cvAlloc( data_size );
	data_size = trainer->m * sizeof( *sorted_weights );
	sorted_weights = (float*) cvAlloc( data_size );
	trimmed_idx = cvCreateMat( 1, trainer->numsamples, CV_32FC1 );

	for ( k = 0; k < trainer->numclasses; k++ ) {
		/* yhat_i = y_i - p_k(x_i), y_i in {0, 1}      */
		/* p_k(x_i) = exp(f_k(x_i)) / (sum_exp_f(x_i)) */
		sum_weights = 0.0F;
		for ( i = 0; i < trainer->numsamples; i++ ) {
			index = icvGetIdxAt( trainer->sampleIdx, i );
			/* p_k(x_i) = 1 / (1 + sum(exp(f_kk(x_i) - f_k(x_i)))), kk != k */
			num = index * trainer->numclasses;
			f_k = (double) trainer->f[num + k];
			sum_exp_f = 1.0;
			for ( kk = 0; kk < trainer->numclasses; kk++ ) {
				if ( kk == k ) { continue; }
				exp_f = (double) trainer->f[num + kk] - f_k;
				exp_f = (exp_f < CV_LOG_VAL_MAX) ? exp( exp_f ) : CV_VAL_MAX;
				if ( exp_f == CV_VAL_MAX || exp_f >= (CV_VAL_MAX - sum_exp_f) ) {
					sum_exp_f = CV_VAL_MAX;
					break;
				}
				sum_exp_f += exp_f;
			}

			val = (float) ( (*((float*) (trainer->ydata + index * trainer->ystep)))
							== (float) k );
			val -= (float) ( (sum_exp_f == CV_VAL_MAX) ? 0.0 : ( 1.0 / sum_exp_f ) );

			assert( val >= -1.0F );
			assert( val <= 1.0F );

			trainer->y->data.fl[index] = val;
			val = (float) fabs( val );
			weights[index] = val * (1.0F - val);
			sorted_weights[i] = weights[index];
			sum_weights += sorted_weights[i];
		}

		sample_idx = trainer->sampleIdx;
		trimmed_num = trainer->numsamples;
		if ( trainer->param[1] < 1.0F ) {
			/* perform weight trimming */

			float threshold;
			int count;

			icvSort_32f( sorted_weights, trainer->numsamples, 0 );

			sum_weights *= (1.0F - trainer->param[1]);

			i = -1;
			do { sum_weights -= sorted_weights[++i]; }
			while ( sum_weights > 0.0F && i < (trainer->numsamples - 1) );

			threshold = sorted_weights[i];

			while ( i > 0 && sorted_weights[i-1] == threshold ) { i--; }

			if ( i > 0 ) {
				trimmed_num = trainer->numsamples - i;
				trimmed_idx->cols = trimmed_num;
				count = 0;
				for ( i = 0; i < trainer->numsamples; i++ ) {
					index = icvGetIdxAt( trainer->sampleIdx, i );
					if ( weights[index] >= threshold ) {
						CV_MAT_ELEM( *trimmed_idx, float, 0, count ) = (float) index;
						count++;
					}
				}

				assert( count == trimmed_num );

				sample_idx = trimmed_idx;

				printf( "k: %d Used samples %%: %g\n", k,
						(float) trimmed_num / (float) trainer->numsamples * 100.0F );
			}
		} /* weight trimming */

		trees[k] = (CvCARTClassifier*) cvCreateCARTClassifier( trainer->trainData,
				   trainer->flags, trainer->y, NULL, NULL, NULL, sample_idx, trainer->weights,
				   (CvClassifierTrainParams*) &trainer->cartParams );

		CV_GET_SAMPLE( *trainer->trainData, trainer->flags, 0, sample );
		CV_GET_SAMPLE_STEP( *trainer->trainData, trainer->flags, sample_step );
		sample_data = sample.data.ptr;
		for ( i = 0; i < trimmed_num; i++ ) {
			index = icvGetIdxAt( sample_idx, i );
			sample.data.ptr = sample_data + index * sample_step;
			idx[index] = (int) cvEvalCARTClassifierIdx( (CvClassifier*) trees[k],
						 &sample );
		}
		for ( j = 0; j <= trees[k]->count; j++ ) {
			respnum = 0;
			val = 0.0F;
			sum_weights = 0.0F;
			for ( i = 0; i < trimmed_num; i++ ) {
				index = icvGetIdxAt( sample_idx, i );
				if ( idx[index] == j ) {
					val += trainer->y->data.fl[index];
					sum_weights += weights[index];
					respnum++;
				}
			}
			if ( sum_weights > 0.0F ) {
				val = ((float) (trainer->numclasses - 1)) * val /
					  ((float) (trainer->numclasses)) / sum_weights;
			} else {
				val = 0.0F;
			}
			trees[k]->val[j] = val;
		}
	} /* for each class */

	cvReleaseMat( &trimmed_idx );
	cvFree( &sorted_weights );
	cvFree( &weights );
	cvFree( &idx );
}


void icvBtNext_XXBCLASS( CvCARTClassifier** trees, CvBtTrainer* trainer ) {
	float alpha;
	int i;
	CvMat* weak_eval_vals;
	CvMat* sample_idx;
	int num_samples;
	CvMat sample;
	uchar* sample_data;
	int sample_step;

	weak_eval_vals = cvCreateMat( 1, trainer->m, CV_32FC1 );

	sample_idx = cvTrimWeights( trainer->weights, trainer->sampleIdx,
								trainer->param[1] );
	num_samples = ( sample_idx == NULL )
				  ? trainer->m : MAX( sample_idx->rows, sample_idx->cols );

	printf( "Used samples %%: %g\n",
			(float) num_samples / (float) trainer->numsamples * 100.0F );

	trees[0] = (CvCARTClassifier*) cvCreateCARTClassifier( trainer->trainData,
			   trainer->flags, trainer->y, NULL, NULL, NULL,
			   sample_idx, trainer->weights,
			   (CvClassifierTrainParams*) &trainer->cartParams );

	/* evaluate samples */
	CV_GET_SAMPLE( *trainer->trainData, trainer->flags, 0, sample );
	CV_GET_SAMPLE_STEP( *trainer->trainData, trainer->flags, sample_step );
	sample_data = sample.data.ptr;

	for ( i = 0; i < trainer->m; i++ ) {
		sample.data.ptr = sample_data + i * sample_step;
		weak_eval_vals->data.fl[i] = trees[0]->eval( (CvClassifier*) trees[0], &sample );
	}

	alpha = cvBoostNextWeakClassifier( weak_eval_vals, trainer->trainClasses,
									   trainer->y, trainer->weights, trainer->boosttrainer );

	/* multiply tree by alpha */
	for ( i = 0; i <= trees[0]->count; i++ ) {
		trees[0]->val[i] *= alpha;
	}
	if ( trainer->type == CV_RABCLASS ) {
		for ( i = 0; i <= trees[0]->count; i++ ) {
			trees[0]->val[i] = cvLogRatio( trees[0]->val[i] );
		}
	}

	if ( sample_idx != NULL && sample_idx != trainer->sampleIdx ) {
		cvReleaseMat( &sample_idx );
	}
	cvReleaseMat( &weak_eval_vals );
}

typedef void (*CvBtNextFunc)( CvCARTClassifier** trees, CvBtTrainer* trainer );

static CvBtNextFunc icvBtNextFunc[] = {
	icvBtNext_XXBCLASS,
	icvBtNext_XXBCLASS,
	icvBtNext_XXBCLASS,
	icvBtNext_XXBCLASS,
	icvBtNext_L2CLASS,
	icvBtNext_LKCLASS,
	icvBtNext_LSREG,
	icvBtNext_LADREG,
	icvBtNext_MREG
};

CV_BOOST_IMPL
void cvBtNext( CvCARTClassifier** trees, CvBtTrainer* trainer ) {
	int i, j;
	int index;
	CvMat sample;
	int sample_step;
	uchar* sample_data;

	icvBtNextFunc[trainer->type]( trees, trainer );

	/* shrinkage */
	if ( trainer->param[0] != 1.0F ) {
		for ( j = 0; j < trainer->numclasses; j++ ) {
			for ( i = 0; i <= trees[j]->count; i++ ) {
				trees[j]->val[i] *= trainer->param[0];
			}
		}
	}

	if ( trainer->type > CV_GABCLASS ) {
		/* update F_(m-1) */
		CV_GET_SAMPLE( *(trainer->trainData), trainer->flags, 0, sample );
		CV_GET_SAMPLE_STEP( *(trainer->trainData), trainer->flags, sample_step );
		sample_data = sample.data.ptr;
		for ( i = 0; i < trainer->numsamples; i++ ) {
			index = icvGetIdxAt( trainer->sampleIdx, i );
			sample.data.ptr = sample_data + index * sample_step;
			for ( j = 0; j < trainer->numclasses; j++ ) {
				trainer->f[index* trainer->numclasses + j] +=
					trees[j]->eval( (CvClassifier*) (trees[j]), &sample );
			}
		}
	}
}

CV_BOOST_IMPL
void cvBtEnd( CvBtTrainer** trainer ) {
	CV_FUNCNAME( "cvBtEnd" );

	__BEGIN__;

	if ( trainer == NULL || (*trainer) == NULL ) {
		CV_ERROR( CV_StsNullPtr, "Invalid trainer parameter" );
	}

	if ( (*trainer)->y != NULL ) {
		CV_CALL( cvReleaseMat( &((*trainer)->y) ) );
	}
	if ( (*trainer)->weights != NULL ) {
		CV_CALL( cvReleaseMat( &((*trainer)->weights) ) );
	}
	if ( (*trainer)->boosttrainer != NULL ) {
		CV_CALL( cvBoostEndTraining( &((*trainer)->boosttrainer) ) );
	}
	CV_CALL( cvFree( trainer ) );

	__END__;
}

/****************************************************************************************\
*                         Boosted tree model as a classifier                             *
\****************************************************************************************/

CV_BOOST_IMPL
float cvEvalBtClassifier( CvClassifier* classifier, CvMat* sample ) {
	float val;

	CV_FUNCNAME( "cvEvalBtClassifier" );

	__BEGIN__;

	int i;

	val = 0.0F;
	if ( CV_IS_TUNABLE( classifier->flags ) ) {
		CvSeqReader reader;
		CvCARTClassifier* tree;

		CV_CALL( cvStartReadSeq( ((CvBtClassifier*) classifier)->seq, &reader ) );
		for ( i = 0; i < ((CvBtClassifier*) classifier)->numiter; i++ ) {
			CV_READ_SEQ_ELEM( tree, reader );
			val += tree->eval( (CvClassifier*) tree, sample );
		}
	} else {
		CvCARTClassifier** ptree;

		ptree = ((CvBtClassifier*) classifier)->trees;
		for ( i = 0; i < ((CvBtClassifier*) classifier)->numiter; i++ ) {
			val += (*ptree)->eval( (CvClassifier*) (*ptree), sample );
			ptree++;
		}
	}

	__END__;

	return val;
}

CV_BOOST_IMPL
float cvEvalBtClassifier2( CvClassifier* classifier, CvMat* sample ) {
	float val;

	CV_FUNCNAME( "cvEvalBtClassifier2" );

	__BEGIN__;

	CV_CALL( val = cvEvalBtClassifier( classifier, sample ) );

	__END__;

	return (float) (val >= 0.0F);
}

CV_BOOST_IMPL
float cvEvalBtClassifierK( CvClassifier* classifier, CvMat* sample ) {
	int cls = 0;

	CV_FUNCNAME( "cvEvalBtClassifierK" );

	__BEGIN__;

	int i, k;
	float max_val;
	int numclasses;

	float* vals;
	size_t data_size;

	numclasses = ((CvBtClassifier*) classifier)->numclasses;
	data_size = sizeof( *vals ) * numclasses;
	CV_CALL( vals = (float*) cvAlloc( data_size ) );
	memset( vals, 0, data_size );

	if ( CV_IS_TUNABLE( classifier->flags ) ) {
		CvSeqReader reader;
		CvCARTClassifier* tree;

		CV_CALL( cvStartReadSeq( ((CvBtClassifier*) classifier)->seq, &reader ) );
		for ( i = 0; i < ((CvBtClassifier*) classifier)->numiter; i++ ) {
			for ( k = 0; k < numclasses; k++ ) {
				CV_READ_SEQ_ELEM( tree, reader );
				vals[k] += tree->eval( (CvClassifier*) tree, sample );
			}
		}

	} else {
		CvCARTClassifier** ptree;

		ptree = ((CvBtClassifier*) classifier)->trees;
		for ( i = 0; i < ((CvBtClassifier*) classifier)->numiter; i++ ) {
			for ( k = 0; k < numclasses; k++ ) {
				vals[k] += (*ptree)->eval( (CvClassifier*) (*ptree), sample );
				ptree++;
			}
		}
	}

	max_val = vals[cls];
	for ( k = 1; k < numclasses; k++ ) {
		if ( vals[k] > max_val ) {
			max_val = vals[k];
			cls = k;
		}
	}

	CV_CALL( cvFree( &vals ) );

	__END__;

	return (float) cls;
}

typedef float (*CvEvalBtClassifier)( CvClassifier* classifier, CvMat* sample );

static CvEvalBtClassifier icvEvalBtClassifier[] = {
	cvEvalBtClassifier2,
	cvEvalBtClassifier2,
	cvEvalBtClassifier2,
	cvEvalBtClassifier2,
	cvEvalBtClassifier2,
	cvEvalBtClassifierK,
	cvEvalBtClassifier,
	cvEvalBtClassifier,
	cvEvalBtClassifier
};

CV_BOOST_IMPL
int cvSaveBtClassifier( CvClassifier* classifier, const char* filename ) {
	CV_FUNCNAME( "cvSaveBtClassifier" );

	__BEGIN__;

	FILE* file;
	int i, j;
	CvSeqReader reader;
	memset(&reader, 0, sizeof(reader));
	CvCARTClassifier* tree;

	CV_ASSERT( classifier );
	CV_ASSERT( filename );

	if ( !icvMkDir( filename ) || (file = fopen( filename, "w" )) == 0 ) {
		CV_ERROR( CV_StsError, "Unable to create file" );
	}

	if ( CV_IS_TUNABLE( classifier->flags ) ) {
		CV_CALL( cvStartReadSeq( ((CvBtClassifier*) classifier)->seq, &reader ) );
	}
	fprintf( file, "%d %d\n%d\n%d\n", (int) ((CvBtClassifier*) classifier)->type,
			 ((CvBtClassifier*) classifier)->numclasses,
			 ((CvBtClassifier*) classifier)->numfeatures,
			 ((CvBtClassifier*) classifier)->numiter );

	for ( i = 0; i < ((CvBtClassifier*) classifier)->numclasses *
			((CvBtClassifier*) classifier)->numiter; i++ ) {
		if ( CV_IS_TUNABLE( classifier->flags ) ) {
			CV_READ_SEQ_ELEM( tree, reader );
		} else {
			tree = ((CvBtClassifier*) classifier)->trees[i];
		}

		fprintf( file, "%d\n", tree->count );
		for ( j = 0; j < tree->count; j++ ) {
			fprintf( file, "%d %g %d %d\n", tree->compidx[j],
					 tree->threshold[j],
					 tree->left[j],
					 tree->right[j] );
		}
		for ( j = 0; j <= tree->count; j++ ) {
			fprintf( file, "%g ", tree->val[j] );
		}
		fprintf( file, "\n" );
	}

	fclose( file );

	__END__;

	return 1;
}


CV_BOOST_IMPL
void cvReleaseBtClassifier( CvClassifier** ptr ) {
	CV_FUNCNAME( "cvReleaseBtClassifier" );

	__BEGIN__;

	int i;

	if ( ptr == NULL || *ptr == NULL ) {
		CV_ERROR( CV_StsNullPtr, "" );
	}
	if ( CV_IS_TUNABLE( (*ptr)->flags ) ) {
		CvSeqReader reader;
		CvCARTClassifier* tree;

		CV_CALL( cvStartReadSeq( ((CvBtClassifier*) *ptr)->seq, &reader ) );
		for ( i = 0; i < ((CvBtClassifier*) *ptr)->numclasses *
				((CvBtClassifier*) *ptr)->numiter; i++ ) {
			CV_READ_SEQ_ELEM( tree, reader );
			tree->release( (CvClassifier**) (&tree) );
		}
		CV_CALL( cvReleaseMemStorage( &(((CvBtClassifier*) *ptr)->seq->storage) ) );
	} else {
		CvCARTClassifier** ptree;

		ptree = ((CvBtClassifier*) * ptr)->trees;
		for ( i = 0; i < ((CvBtClassifier*) *ptr)->numclasses *
				((CvBtClassifier*) *ptr)->numiter; i++ ) {
			(*ptree)->release( (CvClassifier**) ptree );
			ptree++;
		}
	}

	CV_CALL( cvFree( ptr ) );
	*ptr = NULL;

	__END__;
}

void cvTuneBtClassifier( CvClassifier* classifier, CvMat*, int flags,
						 CvMat*, CvMat* , CvMat*, CvMat*, CvMat* ) {
	CV_FUNCNAME( "cvTuneBtClassifier" );

	__BEGIN__;

	size_t data_size;

	if ( CV_IS_TUNABLE( flags ) ) {
		if ( !CV_IS_TUNABLE( classifier->flags ) ) {
			CV_ERROR( CV_StsUnsupportedFormat,
					  "Classifier does not support tune function" );
		} else {
			/* tune classifier */
			CvCARTClassifier** trees;

			printf( "Iteration %d\n", ((CvBtClassifier*) classifier)->numiter + 1 );

			data_size = sizeof( *trees ) * ((CvBtClassifier*) classifier)->numclasses;
			CV_CALL( trees = (CvCARTClassifier**) cvAlloc( data_size ) );
			CV_CALL( cvBtNext( trees,
							   (CvBtTrainer*) ((CvBtClassifier*) classifier)->trainer ) );
			CV_CALL( cvSeqPushMulti( ((CvBtClassifier*) classifier)->seq,
									 trees, ((CvBtClassifier*) classifier)->numclasses ) );
			CV_CALL( cvFree( &trees ) );
			((CvBtClassifier*) classifier)->numiter++;
		}
	} else {
		if ( CV_IS_TUNABLE( classifier->flags ) ) {
			/* convert */
			void* ptr;

			assert( ((CvBtClassifier*) classifier)->seq->total ==
					((CvBtClassifier*) classifier)->numiter *
					((CvBtClassifier*) classifier)->numclasses );

			data_size = sizeof( ((CvBtClassifier*) classifier)->trees[0] ) *
						((CvBtClassifier*) classifier)->seq->total;
			CV_CALL( ptr = cvAlloc( data_size ) );
			CV_CALL( cvCvtSeqToArray( ((CvBtClassifier*) classifier)->seq, ptr ) );
			CV_CALL( cvReleaseMemStorage(
						 &(((CvBtClassifier*) classifier)->seq->storage) ) );
			((CvBtClassifier*) classifier)->trees = (CvCARTClassifier**) ptr;
			classifier->flags &= ~CV_TUNABLE;
			CV_CALL( cvBtEnd( (CvBtTrainer**)
							  &(((CvBtClassifier*) classifier)->trainer )) );
			((CvBtClassifier*) classifier)->trainer = NULL;
		}
	}

	__END__;
}

CvBtClassifier* icvAllocBtClassifier( CvBoostType type, int flags, int numclasses,
									  int numiter ) {
	CvBtClassifier* ptr;
	size_t data_size;

	assert( numclasses >= 1 );
	assert( numiter >= 0 );
	assert( ( numclasses == 1 ) || (type == CV_LKCLASS) );

	data_size = sizeof( *ptr );
	ptr = (CvBtClassifier*) cvAlloc( data_size );
	memset( ptr, 0, data_size );

	if ( CV_IS_TUNABLE( flags ) ) {
		ptr->seq = cvCreateSeq( 0, sizeof( *(ptr->seq) ), sizeof( *(ptr->trees) ),
								cvCreateMemStorage() );
		ptr->numiter = 0;
	} else {
		data_size = numclasses * numiter * sizeof( *(ptr->trees) );
		ptr->trees = (CvCARTClassifier**) cvAlloc( data_size );
		memset( ptr->trees, 0, data_size );

		ptr->numiter = numiter;
	}

	ptr->flags = flags;
	ptr->numclasses = numclasses;
	ptr->type = type;

	ptr->eval = icvEvalBtClassifier[(int) type];
	ptr->tune = cvTuneBtClassifier;
	ptr->save = cvSaveBtClassifier;
	ptr->release = cvReleaseBtClassifier;

	return ptr;
}

CV_BOOST_IMPL
CvClassifier* cvCreateBtClassifier( CvMat* trainData,
									int flags,
									CvMat* trainClasses,
									CvMat* typeMask,
									CvMat* missedMeasurementsMask,
									CvMat* compIdx,
									CvMat* sampleIdx,
									CvMat* weights,
									CvClassifierTrainParams* trainParams ) {
	CvBtClassifier* ptr = 0;

	CV_FUNCNAME( "cvCreateBtClassifier" );

	__BEGIN__;
	CvBoostType type;
	int num_classes;
	int num_iter;
	int i;
	CvCARTClassifier** trees;
	size_t data_size;

	CV_ASSERT( trainData != NULL );
	CV_ASSERT( trainClasses != NULL );
	CV_ASSERT( typeMask == NULL );
	CV_ASSERT( missedMeasurementsMask == NULL );
	CV_ASSERT( compIdx == NULL );
	CV_ASSERT( weights == NULL );
	CV_ASSERT( trainParams != NULL );

	type = ((CvBtClassifierTrainParams*) trainParams)->type;

	if ( type >= CV_DABCLASS && type <= CV_GABCLASS && sampleIdx ) {
		CV_ERROR( CV_StsBadArg, "Sample indices are not supported for this type" );
	}

	if ( type == CV_LKCLASS ) {
		double min_val;
		double max_val;

		cvMinMaxLoc( trainClasses, &min_val, &max_val );
		num_classes = (int) (max_val + 1.0);

		CV_ASSERT( num_classes >= 2 );
	} else {
		num_classes = 1;
	}
	num_iter = ((CvBtClassifierTrainParams*) trainParams)->numiter;

	CV_ASSERT( num_iter > 0 );

	ptr = icvAllocBtClassifier( type, CV_TUNABLE | flags, num_classes, num_iter );
	ptr->numfeatures = (CV_IS_ROW_SAMPLE( flags )) ? trainData->cols : trainData->rows;

	i = 0;

	printf( "Iteration %d\n", 1 );

	data_size = sizeof( *trees ) * ptr->numclasses;
	CV_CALL( trees = (CvCARTClassifier**) cvAlloc( data_size ) );

	CV_CALL( ptr->trainer = cvBtStart( trees, trainData, flags, trainClasses, sampleIdx,
									   ((CvBtClassifierTrainParams*) trainParams)->numsplits, type, num_classes,
									   &(((CvBtClassifierTrainParams*) trainParams)->param[0]) ) );

	CV_CALL( cvSeqPushMulti( ptr->seq, trees, ptr->numclasses ) );
	CV_CALL( cvFree( &trees ) );
	ptr->numiter++;

	for ( i = 1; i < num_iter; i++ ) {
		ptr->tune( (CvClassifier*) ptr, NULL, CV_TUNABLE, NULL, NULL, NULL, NULL, NULL );
	}
	if ( !CV_IS_TUNABLE( flags ) ) {
		/* convert */
		ptr->tune( (CvClassifier*) ptr, NULL, 0, NULL, NULL, NULL, NULL, NULL );
	}

	__END__;

	return (CvClassifier*) ptr;
}

CV_BOOST_IMPL
CvClassifier* cvCreateBtClassifierFromFile( const char* filename ) {
	CvBtClassifier* ptr = 0;

	CV_FUNCNAME( "cvCreateBtClassifierFromFile" );

	__BEGIN__;

	FILE* file;
	int i, j;
	int data_size;
	int num_classifiers;
	int num_features;
	int num_classes;
	int type;

	CV_ASSERT( filename != NULL );

	ptr = NULL;
	file = fopen( filename, "r" );
	if ( !file ) {
		CV_ERROR( CV_StsError, "Unable to open file" );
	}

	fscanf( file, "%d %d %d %d", &type, &num_classes, &num_features, &num_classifiers );

	CV_ASSERT( type >= (int) CV_DABCLASS && type <= (int) CV_MREG );
	CV_ASSERT( num_features > 0 );
	CV_ASSERT( num_classifiers > 0 );

	if ( (CvBoostType) type != CV_LKCLASS ) {
		num_classes = 1;
	}
	ptr = icvAllocBtClassifier( (CvBoostType) type, 0, num_classes, num_classifiers );
	ptr->numfeatures = num_features;

	for ( i = 0; i < num_classes * num_classifiers; i++ ) {
		int count;
		CvCARTClassifier* tree;

		fscanf( file, "%d", &count );

		data_size = sizeof( *tree )
					+ count * ( sizeof( *(tree->compidx) ) + sizeof( *(tree->threshold) ) +
								sizeof( *(tree->right) ) + sizeof( *(tree->left) ) )
					+ (count + 1) * ( sizeof( *(tree->val) ) );
		CV_CALL( tree = (CvCARTClassifier*) cvAlloc( data_size ) );
		memset( tree, 0, data_size );
		tree->eval = cvEvalCARTClassifier;
		tree->tune = NULL;
		tree->save = NULL;
		tree->release = cvReleaseCARTClassifier;
		tree->compidx = (int*) ( tree + 1 );
		tree->threshold = (float*) ( tree->compidx + count );
		tree->left = (int*) ( tree->threshold + count );
		tree->right = (int*) ( tree->left + count );
		tree->val = (float*) ( tree->right + count );

		tree->count = count;
		for ( j = 0; j < tree->count; j++ ) {
			fscanf( file, "%d %g %d %d", &(tree->compidx[j]),
					&(tree->threshold[j]),
					&(tree->left[j]),
					&(tree->right[j]) );
		}
		for ( j = 0; j <= tree->count; j++ ) {
			fscanf( file, "%g", &(tree->val[j]) );
		}
		ptr->trees[i] = tree;
	}

	fclose( file );

	__END__;

	return (CvClassifier*) ptr;
}

/****************************************************************************************\
*                                    Utility functions                                   *
\****************************************************************************************/

CV_BOOST_IMPL
CvMat* cvTrimWeights( CvMat* weights, CvMat* idx, float factor ) {
	CvMat* ptr = 0;

	CV_FUNCNAME( "cvTrimWeights" );
	__BEGIN__;
	int i, index, num;
	float sum_weights;
	uchar* wdata;
	size_t wstep;
	int wnum;
	float threshold;
	int count;
	float* sorted_weights;

	CV_ASSERT( CV_MAT_TYPE( weights->type ) == CV_32FC1 );

	ptr = idx;
	sorted_weights = NULL;

	if ( factor > 0.0F && factor < 1.0F ) {
		size_t data_size;

		CV_MAT2VEC( *weights, wdata, wstep, wnum );
		num = ( idx == NULL ) ? wnum : MAX( idx->rows, idx->cols );

		data_size = num * sizeof( *sorted_weights );
		sorted_weights = (float*) cvAlloc( data_size );
		memset( sorted_weights, 0, data_size );

		sum_weights = 0.0F;
		for ( i = 0; i < num; i++ ) {
			index = icvGetIdxAt( idx, i );
			sorted_weights[i] = *((float*) (wdata + index * wstep));
			sum_weights += sorted_weights[i];
		}

		icvSort_32f( sorted_weights, num, 0 );

		sum_weights *= (1.0F - factor);

		i = -1;
		do { sum_weights -= sorted_weights[++i]; }
		while ( sum_weights > 0.0F && i < (num - 1) );

		threshold = sorted_weights[i];

		while ( i > 0 && sorted_weights[i-1] == threshold ) { i--; }

		if ( i > 0 || ( idx != NULL && CV_MAT_TYPE( idx->type ) != CV_32FC1 ) ) {
			CV_CALL( ptr = cvCreateMat( 1, num - i, CV_32FC1 ) );
			count = 0;
			for ( i = 0; i < num; i++ ) {
				index = icvGetIdxAt( idx, i );
				if ( *((float*) (wdata + index * wstep)) >= threshold ) {
					CV_MAT_ELEM( *ptr, float, 0, count ) = (float) index;
					count++;
				}
			}

			assert( count == ptr->cols );
		}
		cvFree( &sorted_weights );
	}

	__END__;

	return ptr;
}


CV_BOOST_IMPL
void cvReadTrainData( const char* filename, int flags,
					  CvMat** trainData,
					  CvMat** trainClasses ) {

	CV_FUNCNAME( "cvReadTrainData" );

	__BEGIN__;

	FILE* file;
	int m, n;
	int i, j;
	float val;

	if ( filename == NULL ) {
		CV_ERROR( CV_StsNullPtr, "filename must be specified" );
	}
	if ( trainData == NULL ) {
		CV_ERROR( CV_StsNullPtr, "trainData must be not NULL" );
	}
	if ( trainClasses == NULL ) {
		CV_ERROR( CV_StsNullPtr, "trainClasses must be not NULL" );
	}

	*trainData = NULL;
	*trainClasses = NULL;
	file = fopen( filename, "r" );
	if ( !file ) {
		CV_ERROR( CV_StsError, "Unable to open file" );
	}

	fscanf( file, "%d %d", &m, &n );

	if ( CV_IS_ROW_SAMPLE( flags ) ) {
		CV_CALL( *trainData = cvCreateMat( m, n, CV_32FC1 ) );
	} else {
		CV_CALL( *trainData = cvCreateMat( n, m, CV_32FC1 ) );
	}

	CV_CALL( *trainClasses = cvCreateMat( 1, m, CV_32FC1 ) );

	for ( i = 0; i < m; i++ ) {
		for ( j = 0; j < n; j++ ) {
			fscanf( file, "%f", &val );
			if ( CV_IS_ROW_SAMPLE( flags ) ) {
				CV_MAT_ELEM( **trainData, float, i, j ) = val;
			} else {
				CV_MAT_ELEM( **trainData, float, j, i ) = val;
			}
		}
		fscanf( file, "%f", &val );
		CV_MAT_ELEM( **trainClasses, float, 0, i ) = val;
	}

	fclose( file );

	__END__;

}

CV_BOOST_IMPL
void cvWriteTrainData( const char* filename, int flags,
					   CvMat* trainData, CvMat* trainClasses, CvMat* sampleIdx ) {
	CV_FUNCNAME( "cvWriteTrainData" );

	__BEGIN__;

	FILE* file;
	int m, n;
	int i, j;
	int clsrow;
	int count;
	int idx;
	CvScalar sc;

	if ( filename == NULL ) {
		CV_ERROR( CV_StsNullPtr, "filename must be specified" );
	}
	if ( trainData == NULL || CV_MAT_TYPE( trainData->type ) != CV_32FC1 ) {
		CV_ERROR( CV_StsUnsupportedFormat, "Invalid trainData" );
	}
	if ( CV_IS_ROW_SAMPLE( flags ) ) {
		m = trainData->rows;
		n = trainData->cols;
	} else {
		n = trainData->rows;
		m = trainData->cols;
	}
	if ( trainClasses == NULL || CV_MAT_TYPE( trainClasses->type ) != CV_32FC1 ||
			MIN( trainClasses->rows, trainClasses->cols ) != 1 ) {
		CV_ERROR( CV_StsUnsupportedFormat, "Invalid trainClasses" );
	}
	clsrow = (trainClasses->rows == 1);
	if ( m != ( (clsrow) ? trainClasses->cols : trainClasses->rows ) ) {
		CV_ERROR( CV_StsUnmatchedSizes, "Incorrect trainData and trainClasses sizes" );
	}

	if ( sampleIdx != NULL ) {
		count = (sampleIdx->rows == 1) ? sampleIdx->cols : sampleIdx->rows;
	} else {
		count = m;
	}


	file = fopen( filename, "w" );
	if ( !file ) {
		CV_ERROR( CV_StsError, "Unable to create file" );
	}

	fprintf( file, "%d %d\n", count, n );

	for ( i = 0; i < count; i++ ) {
		if ( sampleIdx ) {
			if ( sampleIdx->rows == 1 ) {
				sc = cvGet2D( sampleIdx, 0, i );
			} else {
				sc = cvGet2D( sampleIdx, i, 0 );
			}
			idx = (int) sc.val[0];
		} else {
			idx = i;
		}
		for ( j = 0; j < n; j++ ) {
			fprintf( file, "%g ", ( (CV_IS_ROW_SAMPLE( flags ))
									? CV_MAT_ELEM( *trainData, float, idx, j )
									: CV_MAT_ELEM( *trainData, float, j, idx ) ) );
		}
		fprintf( file, "%g\n", ( (clsrow)
								 ? CV_MAT_ELEM( *trainClasses, float, 0, idx )
								 : CV_MAT_ELEM( *trainClasses, float, idx, 0 ) ) );
	}

	fclose( file );

	__END__;
}


#define ICV_RAND_SHUFFLE( suffix, type )                                                 \
void icvRandShuffle_##suffix( uchar* data, size_t step, int num )                        \
{                                                                                        \
    time_t seed;                                                                         \
    type tmp;                                                                            \
    int i;                                                                               \
    float rn;                                                                            \
                                                                                         \
    time( &seed );                                                                       \
    CvRNG state = cvRNG((int)seed);                                                      \
                                                                                         \
    for( i = 0; i < (num-1); i++ )                                                       \
    {                                                                                    \
        rn = ((float) cvRandInt( &state )) / (1.0F + UINT_MAX);                          \
        CV_SWAP( *((type*)(data + i * step)),                                            \
                 *((type*)(data + ( i + (int)( rn * (num - i ) ) )* step)),              \
                 tmp );                                                                  \
    }                                                                                    \
}

ICV_RAND_SHUFFLE( 8U, uchar )

ICV_RAND_SHUFFLE( 16S, short )

ICV_RAND_SHUFFLE( 32S, int )

ICV_RAND_SHUFFLE( 32F, float )

CV_BOOST_IMPL
void cvRandShuffleVec( CvMat* mat ) {
	CV_FUNCNAME( "cvRandShuffle" );

	__BEGIN__;

	uchar* data;
	size_t step;
	int num;

	if ( (mat == NULL) || !CV_IS_MAT( mat ) || MIN( mat->rows, mat->cols ) != 1 ) {
		CV_ERROR( CV_StsUnsupportedFormat, "" );
	}

	CV_MAT2VEC( *mat, data, step, num );
	switch ( CV_MAT_TYPE( mat->type ) ) {
	case CV_8UC1:
		icvRandShuffle_8U( data, step, num);
		break;
	case CV_16SC1:
		icvRandShuffle_16S( data, step, num);
		break;
	case CV_32SC1:
		icvRandShuffle_32S( data, step, num);
		break;
	case CV_32FC1:
		icvRandShuffle_32F( data, step, num);
		break;
	default:
		CV_ERROR( CV_StsUnsupportedFormat, "" );
	}

	__END__;
}

/* End of file. */
